ACM/ICPC 2011 成都现场赛 Holiday Accommodation 题解
图论题，思路就是，首先把每条边的两端的顶点数统计出来，并且取较小的那一个数，这个数的含义是，最多会有多少对 family 路过这条路。然后用这些数乘以它相应的权值，再乘以 2 就可以了。
由于极端情况下，节点数会达到 105, 路径长度会达到 106, 这已经明显超过 32 位整型了。所以需要用 long long. 需要注意的地方就是，如果两个 int 相乘，其结果可能会达到 long long 的话，那么先把两个 int 分别转换成 long long 再乘。至于为什么就不多解释了。
还有极端情况，比如整棵树退化成了链，100,000 个节点要是深搜的话，就 stack overflow 了。所以需要用栈模拟递归。但是我记得我们队的 WH 在某次练习的时候，用深搜成功解决了这个问题，这有两个方面的原因：一个是他的 dfs 函数没有返回值，并且只有一个参数；二是他是从中间那个顶点开始进行深搜的。所以，他骗分导论学得不错啊。
这道题我 WA 了几次，有因为数组开小了，有因为没有使用栈模拟递归的，还有因为没看清到底是应该使用 %lld 还是 %I64d 的。所以以后一定要吸取教训。
还有就是这道题我写了一个数据生成器，树结构的数据生成器还是比较麻烦。
本题源代码
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 | #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef unsigned long long ull; const int N = 222222; const int M = N << 1; struct glist { int n, m, fe[N], ne[M], he[M], ev[M]; inline void reset(int sz = 0) { memset(fe, -1, sizeof fe); n = sz; m = 0; } inline void insert_directed(int u, int v, int w) { he[m] = v; ev[m] = w; ne[m] = fe[u]; fe[u] = m++; } inline void insert(int u, int v, int w) { insert_directed(u, v, w); insert_directed(v, u, w); } }; glist g; int enc[M]; // Edge node count. struct { int v, e, r; } stk[N]; bool vst[N]; inline void count_node(int index) { int t = 0, w, cnt; memset(enc, 0, sizeof enc); memset(vst, false, sizeof vst); stk[0].v = index; // init stack. __0: vst[stk[t].v] = true; stk[t].r = 1; // result = 1; stk[t].e = g.fe[stk[t].v]; while (stk[t].e != -1) { w = g.he[stk[t].e]; if (!vst[w]) { ++t; stk[t].v = w; goto __0; // ? = dfs(w); __1: cnt = stk[t+1].r; // cnt = dfs(w); stk[t].r += cnt; // result += cnt; enc[stk[t].e>>1] = min(cnt, g.n - cnt); } stk[t].e = g.ne[stk[t].e]; } if (t > 0) { --t; goto __1; // return result; } } int main() { // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int T, n; scanf("%d", &T); for (int k = 1; k <= T; ++k) { scanf("%d", &n); g.reset(n); for (int i = 1; i < n; ++i) { int u, v, w; scanf("%d %d %d", &u, &v, &w); --u; --v; g.insert(u, v, w); } count_node(0); ull result = 0; for (int i = 0; i < g.m; i += 2) result += ull(enc[i>>1]) * ull(g.ev[i]); printf("Case #%d: %llu\n", k, (result * 2ull)); } 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 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 | #include <iostream> #include <cstdlib> #include <cstdio> #include <ctime> using namespace std; const int N = 111111; inline int rnd() { return (rand() * rand()) & 0x7fffffff; } struct tree_generator { int r[N], n; inline void reset(int sz) { n = sz; for (int i = 0; i < n; ++i) r[i] = i; } int find(int x) { return r[x] = (x == r[x] ? x : find(r[x])); } inline void merge(int x, int y) { r[find(x)] = find(y); } inline void generate() { int x, y, w, k; bool flag = true; for (int i = 1; i < n; ++i) { k = 0; flag = true; do { if (++k < 100) x = rnd() % n; else for (x = 0; flag; ++x) { if (find(x) == x) { if (rand() & 1) break; for ( ; find(x) != x; ++x); flag = false; } } y = rnd() % n; } while (find(x) == find(y)); w = rnd() % 1000000 + 1; cout << x + 1 << ' ' << y + 1 << ' ' << w << endl; merge(x, y); if (!(i % 1000)) cerr << i << ' '; } } }; tree_generator generator; int main() { freopen("input.txt", "w", stdout); srand((unsigned int)time(NULL)); int T = 10; cout << T << endl << endl; while (T--) { unsigned int n = rnd() % 98765 + 3; cout << n << endl << endl; cerr << "==== " << T << ':' << n << endl; generator.reset(n); generator.generate(); cout << endl << endl; cerr << endl << endl; } return 0; } |
