本文主要是介绍HDU 3635 Dragon Balls(带权并查集)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目地址：HDU 3635
加权并查集水题。
用num数组维护该城市有多少龙珠，用times数组维护每个龙珠运输了多少次。num数组在合并的时候维护。times数组由于每个都不一样，所以要在找根的时候递归来全部维护。
最终，x龙珠所在的城市就是x节点所在的根，x结点所在的跟的num数组值是该城市的龙珠数。times[x]为该龙珠运输了多少次。
代码如下：
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm>using namespace std;
#define LL long long
int bin[20000], num[20000], times[20000];
int find1(int x)
{int y;if(bin[x]!=x){y=bin[x];bin[x]=find1(bin[x]);times[x]+=times[y];}return bin[x];
}
void join(int x, int y)
{int f1=find1(x);int f2=find1(y);if(f1!=f2){bin[f1]=f2;num[f2]+=num[f1];times[f1]++;}
}
int main()
{int t, nn=0, n, m, i, a, b, f;char c;scanf("%d",&t);while(t--){nn++;scanf("%d%d",&n,&m);for(i=1; i<=n; i++){bin[i]=i;num[i]=1;times[i]=0;}printf("Case %d:\n",nn);while(m--){getchar();scanf("%c",&c);if(c=='T'){scanf("%d%d",&a,&b);join(a,b);}else{scanf("%d",&a);f=find1(a);printf("%d %d %d\n",f,num[f],times[a]);}}}return 0;
}
这篇关于HDU 3635 Dragon Balls(带权并查集)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
