国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > hdu 5606 tree(并查集)

hdu 5606 tree(并查集)

来源:程序员人生   发布时间:2016-07-04 16:07:20 阅读次数:1161次

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5606

tree

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1183    Accepted Submission(s): 527


Problem Description
There is a tree(the tree is a connected graph which contains n points and n1 edges),the points are labeled from 1 to n,which edge has a weight from 0 to 1,for every point i[1,n],you should find the number of the points which are closest to it,the clostest points can contain i itself.
 

Input
the first line contains a number T,means T test cases.

for each test case,the first line is a nubmer n,means the number of the points,next n⑴ lines,each line contains three numbers u,v,w,which shows an edge and its weight.

T50,n105,u,v[1,n],w[0,1]
 

Output
for each test case,you need to print the answer to each point.

in consideration of the large output,imagine ansi is the answer to point i,you only need to output,ans1 xor ans2 xor ans3.. ansn.
 

Sample Input
1 3 1 2 0 2 3 1
 

Sample Output
1 in the sample. $ans_1=2$ $ans_2=2$ $ans_3=1$ $2~xor~2~xor~1=1$,so you need to output 1.
 

Source
BestCoder Round #68 (div.2)


题目大意:

有1个树(n个点,n⑴条边的连通图),有1个树(n个点, n−1条边的联通图),点标号从1~n,树的边权是0或1.求离每一个点最近的点个数(包括自己).


解题思路:1开始想着只要判断w为0就行了,w为0的时候直接给连通的这两个点都加1处理,最后再加上本身这个点就是答案了!!但是这个是毛病的!!!wrong answer!!!
下面解释1下:举1个例子:
    1
 4
 1 2 0
 2 3 0
 1 4 0如果是这组数据的话,我们需要怎样处理呢?如果依照上陈述法计算的话,对1这个点,与其最近的点只有两个,但实际上有3个!!所以就不可以采取上述方法,所以采取并查集的方法,只要w=0就给连通起来。在计算个数便可。

详见代码。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int num[100010]; int fa[100010]; int Find(int x) { if (x!=fa[x]) { return fa[x]=Find(fa[x]); } return x; } void Unit(int x,int y) { x=Find(x); y=Find(y); if (x!=y) { fa[x]=y; num[y]+=num[x];//把两个点连通,同时也要加上子节点在这之前就已连通的点 } } int main() { int t; scanf("%d",&t); while (t--) { int n; scanf("%d",&n); for (int i=1; i<=n; i++) fa[i]=i,num[i]=1; int u,v,w; int s=0; for (int i=1; i<=n⑴; i++) { scanf("%d%d%d",&u,&v,&w); if (w==0) { Unit(u,v); } } for (int i=1; i<=n; i++) { if (fa[i]==i&&num[i]%2==1) s=num[i]^s; } printf ("%d\n",s); } return 0; }



生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生