题目链接：
转载于： （这个博客写的非常好，很详细）
题目大意：
每一个城市都有一颗龙珠，但是随着时间的推移，龙珠会被移到其他的城市，悟空想去收集这些龙珠，但是他需要你告知他，他要找的那颗龙珠的所在的城市，以及这个城市所拥有的龙珠数量，还有这颗龙珠迁移过多少次。
解题分析：
此题的难点在于转移次数的求解，如果暴力让每个转移过的球转移次数+1,会超时，所以，考虑在状态压缩的时候，更新转移次数。某节点的实际转移次数为，该节点现在的转移次数加上它父节点的转移次数。
#include#include #include #include using namespace std;#define N 10010struct node{ int parent; //该节点的父节点 int citynum; //该城市含的球的数量 int transport; //转移次数}p[N];int find(int x){ if (x == p[x].parent) return x; int temp = p[x].parent; p[x].parent = find(p[x].parent); p[x].transport += p[temp].transport; //这点需要反复揣摩，重点,这里不太理解 return p[x].parent;}void join(int x, int y){ int root1, root2; root1 = find(x); root2 = find(y); if(root1!=root2){ p[root1].parent = root2; p[root1].transport=1; //原根节点转移次数置为1 p[root2].citynum += p[root1].citynum; p[root1].citynum = 0; }}int main(){ int ncase=0, T; scanf("%d", &T); while (T--) { int num, querynum; scanf("%d%d", &num, &querynum); for (int i = 1; i <= num; ++i) //初始化 { p[i].parent = i; p[i].citynum = 1; p[i].transport = 0; } printf("Case %d:\n", ++ncase); for (int i = 0; i < querynum; ++i) { char ch; scanf("%*c%c", &ch); //%*c表示只读入，但是不给变量赋值，改成getchar(),也是一样的 if (ch == 'T') { int from, to; scanf("%d%d", &from, &to); join(from, to); } else { int qcity; scanf("%d", &qcity); int ans = find(qcity); printf("%d %d %d\n", ans, p[ans].citynum, p[qcity].transport); } } } return 0;}
2018-07-23