ACM/ICPC 2010 天津现场赛 Building Roads 题解
这道题是一道不错的图论题。其题意是这样的，在给出的一棵无根树中，拆掉其中的一条边（此时原图会变成两棵树），然后保持这条边的长度不变，用这条边将两棵树连接起来。（似乎拆掉之后，如果有必要，还可以连回原来的地方）。然后找到一种拆法，使得进行完这个过程后，整棵树的直径是最短的。题目求的就是这最短的直径是多少。
一开始不太有思路，后来 Google 到一篇文章，大致说了一下这道题和树的直径和半径有关，并且是枚举那条要拆的边。[ALP'10]
然后终于想通：拆掉一条边，之后分别求产生的两棵树的直径、中心和半径。再将两棵树的中心以刚才被拆的边相连，得到的结果就是拆这条边能够得到的最优解。假设拆掉的边的长度为 L, 那两棵树的直径和半径分别为 D1, D2, R1, R2, 那么，得到的结果这棵树的直径是 max{D1, D2, R1 + R2 + L}.
这道题的数据规模比较大，有 10 个 cases, 每个 case 至多能有 2500 个节点。使用这种方法似乎复杂度有 O(n2) 之大，我自己写了一个数据生成器，测试了最极端的数据，也到了将近 30 秒才出解。但是我提交到了 OJ 上，还是过了。可能数据没有想象的那么夸张吧。
本题源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 | #include <queue> #include <cstdio> #include <climits> #include <utility> #include <cstring> using namespace std; const int N = 2555; struct glist { int va[N << 1]; // Edge weight value. int ne[N << 1]; // Next edge of edge. int he[N << 1]; // Head node of edge. int fe[N]; // First edge of node. int n; // Number of nodes, managed manually. int m; // Number of edges, managed by insert(). int dis; // Disabled edge. inline void reset() { memset(fe, -1, sizeof fe); n = 0; m = 0; dis = -1; } inline void insert_single(int u, int v, int value) { va[m] = value; ne[m] = fe[u]; he[m] = v; fe[u] = m++; } inline void insert(int u, int v, int value) { insert_single(u, v, value); insert_single(v, u, value); } inline static int reversed_edge(int e) { return e ^ 1; } inline int tail_vertex(int e) const { return he[reversed_edge(e)]; } inline bool is_disabled_edge(int e) const { if (e == dis || e == reversed_edge(dis)) return true; return false; } }; struct tree_diameter { int v1, v2, dist, prev[N]; bool vst[N]; inline void reset() { v1 = v2 = -1; dist = 0; memset(prev, -1, sizeof prev); } inline void find_max(const glist &g, int u, int &v, int &dist) { v = u; dist = 0; queue<pair<int, int> > qu; qu.push(make_pair(u, 0)); memset(vst, false, sizeof vst); vst[u] = true; while (!qu.empty()) { int x = qu.front().first; int d = qu.front().second; qu.pop(); if (d > dist) { v = x; dist = d; } for (int e = g.fe[x]; e != -1; e = g.ne[e]) { if (g.is_disabled_edge(e)) continue; int y = g.he[e]; if (vst[y]) continue; vst[y] = true; int w = g.va[e]; qu.push(make_pair(y, d + w)); prev[y] = glist::reversed_edge(e); } } } inline void solve(const glist &g, int u = 0) { find_max(g, u, v1, dist); find_max(g, v1, v2, dist); } }; struct tree_radius { int v, dist; inline void reset() { v = -1; dist = 0; } inline void solve(const glist &g, const tree_diameter &diam) { int x = diam.v2, y = -1; v = diam.v2; for (int e = diam.prev[x]; e != -1; e = diam.prev[y]) { if (g.is_disabled_edge(e)) continue; y = g.he[e]; dist += g.va[e]; if ((dist << 1) >= diam.dist) { int dist2 = diam.dist - (dist - g.va[e]); if (dist < dist2) { v = y; } else { v = x; dist = dist2; } return; } x = y; } } }; glist graph; tree_diameter diameter; tree_radius radius; int main() { // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int T, result; scanf("%d", &T); for (int i = 1; i <= T; ++i) { graph.reset(); scanf("%d", &graph.n); result = INT_MAX; int u, v, w; for (int j = 1; j < graph.n; ++j) { scanf("%d %d %d", &u, &v, &w); graph.insert(u, v, w); } int r1, r2, d1, d2, l; for (int e = 0; e < graph.m; e += 2) { v = graph.he[e]; u = graph.tail_vertex(e); graph.dis = e; l = graph.va[e]; diameter.reset(); diameter.solve(graph, u); radius.reset(); radius.solve(graph, diameter); d1 = diameter.dist; r1 = radius.dist; diameter.reset(); diameter.solve(graph, v); radius.reset(); radius.solve(graph, diameter); d2 = diameter.dist; r2 = radius.dist; int t = r1 + r2 + l; if (t < d1) t = d1; if (t < d2) t = d2; if (t < result) result = t; } printf("Case %d: %d\n", i, result); } return 0; } |
自己写的极端数据生成器
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | #include <ctime> #include <cstdio> #include <cstdlib> using namespace std; int main() { freopen("input.txt", "w", stdout); srand(clock()); printf("10\n\n"); // 10 test cases. for (int i = 0; i < 10; ++i) { printf("2500\n"); for (int j = 1; j < 2500; ++j) printf("%d %d %d\n", rand() % j, j, 1 + rand() % 1000); printf("\n"); } return 0; } |
参考
- [ALP'10] alpc32:《天津站B题 Building Roads》
