关键词：
题目地址：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:
",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
",f,num[f],times[a]);
}
}
}
return 0;
}
hdu3635dragonballs（带权并查集）(代码片段)
DragonBallsTimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):10628 AcceptedSubmission(s):3802ProblemDescriptionFivehundredyearslater,thenumberofdragonballswillincreaseunexpectedly,soit‘stoodifficultforMonkeyKing... 查看详情
hdu3635dragonballs(并查集)
DragonBallsTimeLimit:2000/1000ms(Java/Other) MemoryLimit:32768/32768K(Java/Other)TotalSubmission(s):64 AcceptedSubmission(s):26Font: TimesNewRoman | Ve 查看详情
hdu-3635dragonballs并查集(代码片段)
题意：1~N个龙珠，放在1~N个城市，有两种操作：TAB将A所再城市的所有球转移到B所在的城市。QX询问X所在的城市pls，该城市中龙珠数量nm，以及龙珠转移次数trs题解：并查集模板题，顺带更新一些数据。pls不必更新，因为X所在的... 查看详情
hdu1289abug'slife（带权并查集）(代码片段)
HDU1289带权并查集ProblemDescriptionBackgroundProfessorHopperisresearchingthesexualbehaviorofararespeciesofbugs.Heassumesthattheyfeaturetwodifferentgendersandthattheyonlyinteractwithbugsoftheoppositegender. 查看详情
hdu3038howmanyanswersarewrong（带权并查集）
HowManyAnswersAreWrongProblemDescriptionTTandFFare...friends.Uh...veryverygoodfriends-________-bFFisabadboy,heisalwayswooingTTtoplaythefollowinggamewithhim.Thisisaveryhumdrumgame.Tobeginwith,TTshouldw 查看详情
hdu3038howmanyanswersarewrong（带权并查集）
传送门DescriptionTTandFFare...friends.Uh...veryverygoodfriends-________-bFFisabadboy,heisalwayswooingTTtoplaythefollowinggamewithhim.Thisisaveryhumdrumgame.Tobeginwith,TTshouldwritedownasequenceofinteger 查看详情
带权并查集复习-hdu3038
TTandFFare...friends.Uh...veryverygoodfriends-________-bFFisabadboy,heisalwayswooingTTtoplaythefollowinggamewithhim.Thisisaveryhumdrumgame.Tobeginwith,TTshouldwritedownasequenceofintegers-_-!!(bored). 查看详情
hdu3038howmanyanswersarewrong[带权并查集]
HowManyAnswersAreWrongTimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):6336 AcceptedSubmission(s):2391ProblemDes 查看详情
hdu_3172_带权并查集
VirtualFriendsTimeLimit:4000/2000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):8229 AcceptedSubmission(s):2363ProblemDescription 查看详情
hdu2818（带权并查集）
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=2818还是不熟练。。。1#include<cstdio>2#include<cstring>3constintmaxn=30005;4intf[maxn],under[maxn],sum[maxn];56voidinit()7{8for(inti=0;i<=maxn;i++ 查看详情
hdu3038howmanyanswersarewrong——带权并查集
题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=3038 HowManyAnswersAreWrongTimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):1 查看详情
hdu-3038带权并查集
这道题我拖了有8个月...今天放假拉出来研究一下带权的正确性,还有半开半闭的处理还有ab指向的一系列细节问题#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>usingnamespacestd;constintmaxn=200010;intp[maxn],r[m 查看详情
带权并查集hdu3047zjnustadium
http://acm.hdu.edu.cn/showproblem.php?pid=3047【题意】http://blog.csdn.net/hj1107402232/article/details/9921311【Accepted】1#include<iostream>2#include<cstdio>3#include<cstring>4#include&l 查看详情
hdu3038howmanyanswersarewrong(带权并查集)(代码片段)
HowManyAnswersAreWrongTimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):14876 AcceptedSubmission(s):5237ProblemDe 查看详情
hdu3038：howmanyanswersarewrong(带权并查集)(代码片段)
HowManyAnswersAreWrongTimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):16338 AcceptedSubmission(s):5724题目链接：http 查看详情
hdu-3038/3048（带权并查集）（待补）
题目链接：点我点我题意：题解：两题代码差不多，放个3047的。1#include<cstdio>2#include<iostream>3#include<algorithm>4usingnamespacestd;56constintN=200010;7intFather[N],value[N];89intfind(intx){10if(x==Father[x]) 查看详情
hdu3047zjnustadium（带权并查集，难想到）(代码片段)
M-ZjnuStadiumTimeLimit:1000MS MemoryLimit:32768KB 64bitIOFormat:%I64d&%I64uSubmitStatusDescriptionIn12thZhejiangCollegeStudentsGames2007,therewasanews 查看详情
hdu3038howmanyanswersarewrong（带权并查集）
题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=1272题目大意：有n条信息，每条信息都给出区间l到r的值，如果后面出现的信息与前面的矛盾，那么就算是一个错误信息，问一共给出多少错误信息。比如1给出三条信息1410，125，346... 查看详情