首页 > 代码库 > Hdu 3635 Dragon Balls (并查集)
Hdu 3635 Dragon Balls (并查集)
Problem地址:http://acm.hdu.edu.cn/showproblem.php?pid=3635
看完此题,首先要明确这题要输出三个量:A号球所在的城市编号X,以及X城市有多少球,接着是A号球被运送的次数
第一个问题很好说,用并查集轻而易举。问题在第二个和第三个。
先解决第二个,思考:什么时候城市的球数会发生变化?
答案很明显,当然是将球从一个城市移到另一个城市的时候。那么可以运用这个特点解决,假设一个city[]数组,初始化全为1,即假设每个城市有一个球。如果将x城市的球移到y时,即city[y] += city[x]。第二个问题就这样解决了。
接着解决第三个问题。我们在并查集的基础上思考,可以认为每次移动时,父亲节点移动一个单位,其子节点的移动距离为其父亲节点距离之和。好像自己都说不清了。。。。。。上图吧:
假设1,2,3,4四个城市。每个城市的球移动次数为0;
将1移到2,1号球的移动次数为1;
再将2移到3,
则2的移动次数为1
此时1的移动次数为1的移动次数加父亲节点2和3的移动次数,其值和为2。
思路就是这样,好像用文字说不清楚。。。只能用图了。
顺便说一句,推荐用C++提交。不知为何,用G++会超时。
#include <iostream>#include <cstring>#include <cstdio>using namespace std;const int MAXN = 10000 + 50;int used[MAXN];int dis[MAXN];int city[MAXN];int Find( int n ){ int i; if( used[n]!=n ){ i = used[n]; used[n] = Find(used[n]); dis[n] += dis[i]; //根据父亲节点算移动次数 } return used[n];}int main(){ int T; int N, Q; char c; int A,B; int x,y; int cases = 0; cin>>T; while(T--){ scanf("%d%d",&N,&Q); for( x=0;x<=N;x++ ){ dis[x] = 0; city[x] = 1; used[x] = x; } //初始化 cases++; printf("Case %d:\n",cases); while(Q--){ //scanf("%c",&c); cin>>c; if( c==‘T‘ ){ scanf("%d%d",&A,&B); x = Find(A); y = Find(B); if( x!=y ){ dis[x]=1; used[x]=y; city[y] += city[x]; //y城市的球数加上x城市的球数 } } else if( c==‘Q‘ ){ scanf( "%d",&A ); x = Find(A); printf("%d %d %d\n",x,city[x],dis[A]); //输出 } } } return 0;}
Hdu 3635 Dragon Balls (并查集)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。