关键词：
Dragon Balls
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4165 Accepted Submission(s): 1603
His country has N cities and there are exactly N dragon balls in the world. At first, for the ith dragon ball, the sacred dragon will puts it in the ith city. Through long years, some cities‘ dragon ball(s) would be transported to other cities. To save physical strength WuKong plans to take Flying Nimbus Cloud, a magical flying cloud to gather dragon balls.
Every time WuKong will collect the information of one dragon ball, he will ask you the information of that ball. You must tell him which city the ball is located and how many dragon balls are there in that city, you also need to tell him how many times the ball has been transported so far.
For each case, the first line contains two integers: N and Q (2 < N <= 10000 , 2 < Q <= 10000).
Each of the following Q lines contains either a fact or a question as the follow format:
T A B : All the dragon balls which are in the same city with A have been transported to the city the Bth ball in. You can assume that the two cities are different.
Q A : WuKong want to know X (the id of the city Ath ball is in), Y (the count of balls in Xth city) and Z (the tranporting times of the Ath ball). (1 <= A, B <= N)
2 3 3 T 1 2 T 3 2 Q 2 3 4 T 1 2 Q 1 T 1 3 Q 1
Case 1: 2 3 0 Case 2: 2 2 13 3 2
题意：题意：刚開始每一个city都有一个相应编号的球，如今给出2个命令，一个是T A B 将A所在的城市里的全部球转移到B球所在的城市， 一个是C A 要求输出A球所在的城市的编号和该城市共同拥有多少个球，以及A球被转移的次数。
思路：首先这里刚開始球的编号和城市的编号一一相应，要想到并查集的方法，其次对于T命令的操作就是合并A和B的城市， 仅仅要将统计城市球数的数组更新一下就可以，并对A城市的根节点所在的球的转移次数设置为1 ， 由于显然这个根节点所相应的球是第一次被转移，难点在于其它的球的转移次数须要依据这个根节点的转移次数来求出。
关键就是路径压缩了，要想求某个球的转移次数，须要对它进行路径的更新， 一直更新到它的根节点，依据根节点的转移次数为1，回溯递推出要求的球的转移次数。 加权并查集，，递归的过程好难理解。 2015,7,23
#include<stdio.h> #include<string.h> #define M 10100 int f[M],time[M],city[M];//分别存放，父节点。转移次数，城市里边的珠子总数 void init() { for(int i=0;i<M;i++){ f[i]=i;//父节点初始化为自己 city[i]=1;//開始的时候每一个城市有一个球 time[i]=0; } } int find(int k) { if(f[k]!=k) { int temp=find(f[k]);//找到根节点 time[k]+=time[f[k]];//子节点的转移次数加上父节点的转移次数 f[k]=temp;//压缩路径，父节点直接指向根节点 } return f[k]; } void merge(int a,int b) { int x=find(a); int y=find(b); if(x!=y) { f[x]=y; time[x]=1;//第一次转移 city[y]+=city[x]; city[x]=0; } } int main() { int t,v=1,i,a,b,c,n,m; char ch[5]; scanf("%d",&t); while(t--) { init(); printf("Case %d: ",v++); scanf("%d%d",&n,&m); for(i=0;i<m;i++) { scanf("%s",ch); if(ch[0]=='Q') { int k; scanf("%d",&c); k=find(c); printf("%d %d %d ",k,city[k],time[c]); } if(ch[0]=='T') { scanf("%d%d",&a,&b); merge(a,b); } } } return 0; }
hdu3635dragonballs(并查集)
DragonBallsTimeLimit:2000/1000ms(Java/Other) MemoryLimit:32768/32768K(Java/Other)TotalSubmission(s):64 AcceptedSubmission(s):26Font: TimesNewRoman | Ve 查看详情
hdu3635dragonballs(带权并查集)
题目地址：pid=3635">HDU3635加权并查集水题。用num数组维护该城市有多少龙珠，用times数组维护每一个龙珠运输了多少次。num数组在合并的时候维护。times数组因为每一个都不一样。所以要在找根的时候递归来所有维护。终于，x龙... 查看详情
hdu3635dragonballs（带权并查集）(代码片段)
DragonBallsTimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):10628 AcceptedSubmission(s):3802ProblemDescriptionFivehundredyearslater,thenumberofdragonballswillincreaseunexpectedly,soit‘stoodifficultforMonkeyKing... 查看详情
hdu-3635dragonballs并查集(代码片段)
题意：1~N个龙珠，放在1~N个城市，有两种操作：TAB将A所再城市的所有球转移到B所在的城市。QX询问X所在的城市pls，该城市中龙珠数量nm，以及龙珠转移次数trs题解：并查集模板题，顺带更新一些数据。pls不必更新，因为X所在的... 查看详情
hdu3635
题目链接：HDU-36351#include<cstdio>2#include<cstring>3constintmaxn=10010;4intf[maxn],ct[maxn],trans[maxn];5intn,m;6voidinit()7{8for(inti=0;i<=n;i++)9{10f[i]=i;11ct[i]=1;12trans[i]=0;13}14}15 查看详情
hdu3635(代码片段)
/*一开始第a个球在第a个城市操作Tab，把第a个球所在城市的所有球移到b所在的城市操作Qa要求输出第a个球在哪个城市第a个球所在的城市有几个球第a个球移动次数*/#include<iostream>#include<cstring>#include<cstdio>#definemovemovee#... 查看详情
poj3635fulltank?
FullTank?TimeLimit:1000MS MemoryLimit:65536KTotalSubmissions:7543 Accepted:2444DescriptionAftergoingthroughthereceiptsfromyourcartripthroughEuropethissummer,yourealisedthatthegaspricesvaried 查看详情
poj3635优先队列+打标记+广搜
AftergoingthroughthereceiptsfromyourcartripthroughEuropethissummer,yourealisedthatthegaspricesvariedbetweenthecitiesyouvisited.Maybeyoucouldhavesavedsomemoneyifyouwereabitmorecleveraboutwhereyoufilled 查看详情
uvalive3635pie
https://vjudge.net/problem/UVALive-3635题意：有F+1个人要分n个蛋糕，他们得到的蛋糕的面积必须是一样的，但是每个蛋糕必须是整块的蛋糕，而不是有多块蛋糕拼成的，蛋糕的形状也可以不相同。给出n块蛋糕各自的半径，求他们每个人... 查看详情
la3635派
题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1636题意：f+1个人，来分n个圆形派，每个人只能从一个派中拿，也就是说，不能从两个里面去拼。求每个人最大的面积。分析：二... 查看详情
poj3635fulltank?[分层图最短路]
FullTank?TimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 7248 Accepted: 2338DescriptionAftergoingthroughthereceiptsfromyourcartripthroughEuropethissummer,yourealis 查看详情
图论补完计划poj3635（最短路变形）
FullTank?TimeLimit:1000MS MemoryLimit:65536KTotalSubmissions:7427 Accepted:2399DescriptionAftergoingthroughthereceiptsfromyourcartripthroughEuropethissummer,yourealisedthatthegaspricesvaried 查看详情
uvalive-3635-pie（二分）
题意：有F+1（1<=F<=10000）个人分N（1<=N<=10000）个圆形派，每个人得到的派面积相同，且必须是一整块（不能够两个甚至多个派拼在一起），求每个人最多能得到多大面积的派。（误差最多到0.001）因为答案是小数类型的... 查看详情
la3635pie(二分法)
链接：http://vjudge.net/problem/33697分析：二分答案。假设每个人得到派的最大面积是x，判断是否能满足F+1个人（因为派是不可以拼起来的，所以一个半径为r的派只能切出[πr²/x]个派，其他部分就浪费了）。1#include<cstdio>2#in... 查看详情
ob3635/ob2530pap/ob3398昂宝电子设计
OB3635MCPA 4-7X1W过认证 //QQ2892715427//输入电压：100-264VAC输入电流：＜0.1APF ＞0.5输出电压：12-25V输出电流：0.26-0.3A空载电压：＜40V 空载功率:＜0.1W 恒流精度： ±5%效率： ＞88% 启动时间：＜1S 耐压：... 查看详情
昂宝ob3635ampob33398mp大功率投光灯80w驱动照明
昂宝OB3635AMP、OB33398MP大功率投光灯80W驱动照明、QQ 2892715427 InputCharacteristics ACinputvoltagerating100Vac~240Vac ACinputvoltagerange90Vac~264Vac ACinputfrequencyrange47Hz~63Hz1.2 查看详情
zoj-3635cinemainakiba（树状数组+二分）
题意：已知有n个人，从第一个人开始每个人被安排在第ai个空座上，有m组询问，问某人所坐的位置。分析：1、用树状数组维护空座的个数，方法：将所有的空座初始化为1，sum（x）则表示从座位1到座位x空座的个数。2、对于每... 查看详情
poj3635fulltank?(代码片段)
【题解】 用dijkstra算法求最短路。同时考虑在每个节点加油（一单位）与否。【代码】1#include<iostream>2#include<map>3#include<cstring>4#include<string>5#include<queue>6usingnamespacestd;7#definemaxn10058#definemaxm10... 查看详情