Problem G - Flight Planning
Time limit: X seconds
The airline company NCPC Airways has flights to and from n
cities, numbered from 1 to n, around the entire world. However,
they only have n - 1 different flights (operating in both
directions), so in order to travel between any two cities you might
have to take several flights. In fact, since the management has made
sure that it's possible to travel between any pair of cities, there is
exactly one set of flights a passenger have to take in order to travel
between two cities (assuming you want to use the same airline).
Recently many of NCPC Airways frequent flyers have complained that
they have had to change flights too often to get to their final
destination. Since NCPC Airways doesn't want to loose their customers
to other airline companies, but still keep the nice property of their
flights, they have decided to cancel one of their current flights and
replace it with another flight. Help the company by writing a program
which finds the best flight to cancel and the best new flight to add
so that the maximum number of flight changes a passenger might have to
make when travelling between any pair of cities in which NCPC Airways
operates is minimized.
The input will be constructed so that it is always possible to
improve the maximum number of flight changes needed.
Input
The first line of the input file contains an integer N (N<20) which denotes the total number of test cases.
The description of each test case is given below:
The first line of input for each test case contains the integer n (4 ≤ n
≤ 2500), the number of cities NCPC Airways operates in. Then
follow n - 1 lines specifying the flights. Each flight is given
as a pair of cities a and b (1 ≤ a, b ≤ n).
Output
For each test case print three lines of output. The first line should
contain an integer, the minimum number of flights needed to take when
travelling between any pair of cities after changing one of the
flights. The second line should contain two integers, specifying the
two cities between which the flight should be canceled. The third
line should contain two integers, specifying the two cities where a
new flight should be added.
If there are more than one optimal solution, any one of them will be accepted.
Sample Input
2
4
1 2
2 3
3 4
14
1 2
1 8
2 3
2 4
8 9
8 10
8 11
4 5
4 6
4 7
10 12
10 13
13 14
Sample Output
2
3 4
2 4
5
1 8
2 10
The 2009 ACM Nordic Collegiate Programming Contest
題目描述：
給一個樹狀的航班，由於旅客抱怨有些兩地飛行轉機的次數太多，因此航空公司打算取消其中一個航班，
並且可以多一個新航班，使得最多轉機次數下降。
並且輸出取消哪個航班，增加哪個航班，而改善後最多轉機次數為何？
如果有多組解，任何一組都可以。
題目解法：
題目意即就是找樹的最長路徑，然後將最長路徑上的邊去除掉，並且增加一點邊，使得最長路徑
後面是我的菜英文說明，不過我相信沒有辦法解釋得很好。
整體效率為 O(n)。
首先把樹轉換成有根樹，即有一個點是 root，其他點存在父子關係。
對於每個點 node 存放數個訊息：(node 有多個子樹，一個父節點)
1) 從子樹來的最長路徑，保留 1st, 2nd, 3rd 長
2) 從父節點來的最長路徑(可能會從某一個葉節點到 root 再到父節點其中不經過 node)
3) 把子樹當作一個圖，存在的最長路徑，保留 1st, 2nd 長 (此路徑不經過 node)
4) 將自己當作子樹從原圖替除後，該圖存在的最長路徑 (此路徑不經過 node)
其中 1, 2 點就不多作說明，用一個 dfs O(n) 便可對於所有點得到這些訊息。
對於第 3 點來說，子樹的最長路徑不一定經過子節點，因此考慮經過與不經過
因此為 max(子節點的第3點答案, 將子樹的第1點的 1st+2nd = 經過子節點的最長路徑)
對於第 4 點來說，一樣考慮有沒有經過父節點
因此為 max(父節點的第4點答案, 將父節點第2點答案+對於父節點子樹中的最長路徑)
以及 max(從葉節點到父節點最長兩條路徑加起來，但不經過 node)
接下來就是窮舉 O(n) 的取消航班，而可以用 O(1) 計算取消後最長路徑為何。
當取消一個航班後，樹會劃分成兩棵，對於兩個樹的中心(最長路的中間點)相連，一定是最佳解。
因此目標是在 O(1) 時間內找到兩棵樹的最長路徑。
因此窮舉邊 s-t，s 是 t 的子節點，因此對於有 s 的子圖的最長路徑
可以從 s 節點資訊中的第1點和第3點得到
對於 t 比較複雜，由於先前都是考慮不經過 t 的情況，因此要從
第 1 點的其中兩條合併成路徑，以及第 4 點的答案，或者是第 2 點 + 第 1 點其中一條路徑
又或者是第 3 點其中一個子樹中的最長路徑。
所有情況考慮後，得到分別兩張圖最長路徑，然後將中心連起來。
by Dynamic programming in O(n).
I also spend a lot of time solving this problem. Finally, I think that maybe this problem same as
uva 10459 - The Tree Root. But it is more difficult than uva 10459.
I find some people that solved by brute-force.
1) find a edge on longest path
2) using the algorithm find two trees' diameter. O(n), you know.
but this way maybe O(n*n).
1. Try to make graph become a rooted tree
2. Find some information of each node.
For node X.
information 1: all X's son node max height(longest path).
information 2: the longest path from parent, but don't have X.
above, you will learn from uva 10459.
information 3: X's son's sub-tree regard as a new graph, how longest path in this graph?
information 4: (G) - (X's sub-tree) regard as a new graph, how longest path in this graph?
3. try cut every edge (i, j), then using information 1-4 find the longest path for two graph.
all step by O(n).
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
vector<int> g[2505];
int dp_down[2505][3], dp_up[2505];
//int arg_dpd[2505][2], arg_dpu[2505];
int dp_ldown[2505][2], dp_lup[2505];
//node as a root, then sub-tree has longest path.
//but dp_ldown, dp_lup not include root.
int cutx, cuty, cut;
void dfs1(int nd, int p) {
for(vector<int>::iterator it = g[nd].begin();
it != g[nd].end(); it++) {
if(*it == p) continue;
dfs1(*it, nd);
if(dp_down[nd][2] < dp_down[*it][0]+1)
dp_down[nd][2] = dp_down[*it][0]+1;
if(dp_down[nd][1] < dp_down[nd][2])
swap(dp_down[nd][1], dp_down[nd][2]);
if(dp_down[nd][0] < dp_down[nd][1])
swap(dp_down[nd][0], dp_down[nd][1]);
int hh = max(dp_ldown[*it][0], dp_down[*it][0]+dp_down[*it][1]);
if(dp_ldown[nd][1] < hh)
dp_ldown[nd][1] = hh;
if(dp_ldown[nd][0] < dp_ldown[nd][1])
swap(dp_ldown[nd][0], dp_ldown[nd][1]);
}
}
void dfs2(int nd, int p, int h, int vg) {
dp_up[nd] = h;
dp_lup[nd] = vg;
//printf("[%2d] %d %d %d\n", nd, dp_lup[nd], dp_ldown[nd][0], dp_ldown[nd][1]);
for(vector<int>::iterator it = g[nd].begin();
it != g[nd].end(); it++) {
if(*it == p) continue;
int hv = dp_up[nd], gv = dp_lup[nd];
if(dp_down[*it][0]+1 == dp_down[nd][0]) {
hv = max(hv, dp_down[nd][1]);
gv = max(gv, dp_up[nd]+dp_down[nd][1]);
} else {
hv = max(hv, dp_down[nd][0]);
gv = max(gv, dp_up[nd]+dp_down[nd][0]);
}
if(dp_down[nd][0] == dp_down[*it][0]+1) {
gv = max(gv, dp_down[nd][1]+dp_down[nd][2]);
} else if(dp_down[nd][1] == dp_down[*it][0]+1) {
gv = max(gv, dp_down[nd][0]+dp_down[nd][2]);
} else {
gv = max(gv, dp_down[nd][0]+dp_down[nd][1]);
}
int hh = max(dp_ldown[*it][0], dp_down[*it][0]+dp_down[*it][1]);
if(hh == dp_ldown[nd][0])
gv = max(gv, dp_ldown[nd][1]);
else
gv = max(gv, dp_ldown[nd][0]);
dfs2(*it, nd, hv+1, gv);
}
}
void sdfs(int nd, int p) {
for(vector<int>::iterator it = g[nd].begin();
it != g[nd].end(); it++) {
if(*it == p) continue;
sdfs(*it, nd);
int s, t;
s = dp_ldown[*it][0];
s = max(s, dp_down[*it][0]+dp_down[*it][1]);
t = dp_lup[nd];
if(dp_down[*it][0]+1 == dp_down[nd][0])
t = max(t, dp_up[nd]+dp_down[nd][1]);
else
t = max(t, dp_up[nd]+dp_down[nd][0]);
int hh = max(dp_ldown[*it][0], dp_down[*it][0]+dp_down[*it][1]);
if(hh == dp_ldown[nd][0])
t = max(t, dp_ldown[nd][1]);
else
t = max(t, dp_ldown[nd][0]);
if(dp_down[*it][0]+1 == dp_down[nd][0])
t = max(t, dp_down[nd][1]+dp_down[nd][2]);
else if(dp_down[*it][0]+1 == dp_down[nd][1])
t = max(t, dp_down[nd][0]+dp_down[nd][2]);
else
t = max(t, dp_down[nd][0]+dp_down[nd][1]);
int newlong = max(max(s, t), (s+1)/2+(t+1)/2+1);
//if(nd == 1278 && *it == 1854)
//printf("%2d<->%2d %d %d %d\n", nd, *it, s, t, newlong);
if(newlong < cut) {
cut = newlong;
cutx = nd, cuty = *it;
}
}
}
int getCenter(int s, int t, int n) {
int i, j;
int indeg[2505] = {};
for(i = 1; i <= n; i++) {
//printf("%d : ", i);
for(j = 0; j < g[i].size(); j++) {
if(i == t && g[i][j] == s) continue;
if(i == s && g[i][j] == t) continue;
indeg[g[i][j]]++;
//printf("%d ", g[i][j]);
}
// puts("");
}
int st[2505] = {};//1->s, 0->t
queue<int> Q;
Q.push(s);
st[s] = 1;
while(!Q.empty()) {
int tn = Q.front();
Q.pop();
for(i = 0; i < g[tn].size(); i++) {
if(g[tn][i] == t) continue;
if(st[g[tn][i]] == 0) {
st[g[tn][i]] = 1;
Q.push(g[tn][i]);
}
}
}
int linkx, linky;
for(i = 1; i <= n; i++) {
if(st[i] == 1 && indeg[i] <= 1)
Q.push(i);
}
while(!Q.empty()) {
int tn = Q.front();
Q.pop();
linkx = tn;
//printf("ss %d\n", tn);
for(i = 0; i < g[tn].size(); i++) {
if(st[g[tn][i]] == 0) continue;
if(--indeg[g[tn][i]] == 1)
Q.push(g[tn][i]);
}
}
for(i = 1; i <= n; i++) {
if(st[i] == 0 && indeg[i] <= 1)
Q.push(i);
}
while(!Q.empty()) {
int tn = Q.front();
Q.pop();
linky = tn;
//printf("tt %d\n", tn);
for(i = 0; i < g[tn].size(); i++) {
if(st[g[tn][i]] == 1) continue;
if(--indeg[g[tn][i]] == 1)
Q.push(g[tn][i]);
}
}
printf("%d %d\n", linkx, linky);
}
int main() {
int testcase;
int n, x, y;
int i, j, k;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d", &n);
for(i = 1; i <= n; i++) {
g[i].clear();
dp_down[i][0] = dp_down[i][1] = dp_down[i][2] = 0;
dp_up[i] = 0;
dp_ldown[i][0] = dp_ldown[i][1] = 0;
dp_lup[i] = 0;
}
for(i = 1; i < n; i++) {
scanf("%d %d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
cut = 0xfffffff;
cutx = -1, cuty = -1;
dfs1(1, 0);
dfs2(1, 0, 0, 0);
sdfs(1, 0);
printf("%d\n", cut);
printf("%d %d\n", cutx, cuty);
getCenter(cutx, cuty, n);
}
return 0;
}
/*
5
15
11 9
8 7
8 14
4 11
10 8
8 4
13 3
2 15
12 3
3 1
8 6
5 14
15 10
8 3
*/
文章定位：
