本文主要是介绍hdu3635Dragon Balls，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
并查集
对于转移次数，开始我自以为想出了一个效率很高的解法,就是在路径压缩的时候统计结点所在的层数，加到该结点的times值里面，也就是这样：
自己感觉还很良好，因为这样效率和原来几乎差不多，交上去却wa，原来，是没有考虑这样的情况：
如果在结点E或F进行查找并且压缩路径，就会成为这样(以find(e)为例)：
这样在这里得到的C B E F的times值都是正确的，但求D的times值时就会得到错误的结果。
这里关键是并查集对应的树的形态的问题，事实上，这里的搜索树形态可以是任意的，而不是第一张图里面的单链形式，因为对于每条链的合并，都可以是在调用根结点时进行的，这时就不涉及路径压缩，于是各种各样形态的图都有可能出现（比如第二张图，可以由dc fe cb ba 的命令得到）。。。
哪怎么办呢？如何得到正确答案又提高效率呢？可行的办法是记录一个结点的根结点，然后在计算的时候把根结点的移动另外加上。。不过我的版本没有这个——我没有用路径压缩，结果实际上慢不了多少。。。额，感觉这句话一说前面说的都变成废话了。。。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int MAX =10005;int last[MAX],amount[MAX],times[MAX],which,all,n,m,move;void make(int n){for(int i=1;i<=n;i++){last[i]=i,amount[i]=1,times[i]=0;}
}int find(int x){if(x==last[x]){which=x;return 0;}int layer=find(last[x]);//times[x]+=layer;//开始的想法，错误的//last[x]=which;//路径压缩return layer+1;
}void un(int a,int b){amount[b]+=amount[a];last[a]=b;
}int main(){int T,a,b,aa,bb,cases=1;char com[20];scanf("%d",&T);while(T--){printf("Case %d:\n",cases++);scanf("%d %d",&n,&m);getchar();make(n);for(int i=0;i<m;i++){scanf("%s",com);if(com[0]=='T'){scanf("%d %d",&a,&b);find(a),aa=which;find(b),bb=which;if(aa!=bb)un(aa,bb);}else if(com[0]=='Q'){scanf("%d",&a);move=find(a);printf("%d %d %d\n",which,amount[which],last[a]==a?0:(move));}}}return 0;
}
这篇关于hdu3635Dragon Balls的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
