《算法竞赛-训练指南》第三章-3.6_LA 3027(并查集)

发布时间:2016-12-8 20:00:11 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"《算法竞赛-训练指南》第三章-3.6_LA 3027(并查集)",主要涉及到《算法竞赛-训练指南》第三章-3.6_LA 3027(并查集)方面的内容,对于《算法竞赛-训练指南》第三章-3.6_LA 3027(并查集)感兴趣的同学可以参考一下。

这道题目也是比较不错的,就是会用到路径压缩的并查集,然后用d[u]记录上到父节点的距离,在每次路径压缩的过程中就把距离叠到你要求的结点。 这个看了代码以后,就比较简单了: #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <string> using namespace std; const int MAXN = 20000 + 11; int N; int f[MAXN]; int d[MAXN]; void init() { for (int i = 1; i <= N; i++) { f[i] = i; d[i] = 0; } } int find(int x) { if (f[x] != x) { int root = find(f[x]); d[x] += d[f[x]]; return f[x] = root; } else { return x; } } int main() { int T; int u, v; char str[11]; scanf("%d", &T); while (T--) { scanf("%d", &N); init(); while (scanf("%s", str) == 1) { if (str[0] == 'O') { break; } else if (str[0] == 'E') { scanf("%d", &u); find(u); printf("%d\n", d[u]); } else if (str[0] == 'I') { scanf("%d%d", &u, &v); f[u] = v; d[u] = abs(v - u) % 1000; } } } system("pause"); return 0; }

上一篇:Android 模拟系统事件(二)
下一篇:基本内部命令

相关文章

相关评论