hdu3367Pseudoforest(最小生成树吧）

http://acm.hdu.edu.cn/showproblem.php?pid=3367

题意是让找出最大的森林也就是符合它所要求的最大的边和它要求每个连通块最多有一个圈就是一个环可以用并查集判祖先

1 如果两个节点是一个祖先就是一个连通块如果有圈肯定不能合并不然就两个圈了就是这条边不要

2 不是一个祖先如果是全都没圈直接合并有一个有的合并加标记为此块有圈

View Code

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<string.h>
 4 #include<algorithm>
 5 using namespace std;
 6 struct node
 7 {
 8     int u,v,c;
 9 }q[100011];
10 int f[100001],father[10011],r[10011];
11 int find(int x)
12 {
13     if(x!=father[x])
14     father[x] = find(father[x]);
15     return father[x];
16 }
17 bool cmp(node a,node b)
18 {
19     return a.c>b.c;
20 }
21 int main()
22 {
23     int i,j,k,n,m;
24     while(scanf("%d%d",&n,&m)!=EOF)
25     {
26         if(n==0&&m==0)
27         break;
28         memset(f,0,sizeof(f));
29         int sum = 0;
30         for(i = 0; i < n; i++)
31         {
32             father[i] = i;
33             r[i] = 0;
34         }
35         for(i = 1; i <= m; i++)
36         {
37             scanf("%d%d%d",&q[i].u,&q[i].v,&q[i].c);
38         }
39         int num = 0;
40         sort(q+1,q+m+1,cmp);
41         for(i = 1; i <= m; i++)
42         {
43             int px = find(q[i].u);
44             int py = find(q[i].v);
45             if(px!=py)
46             {
47                 if(!r[px]&&!r[py]||r[py]&&!r[px]||r[px]&&!r[py])
48                 {
49                     if(r[py]&&!r[px]||r[px]&&!r[py])
50                     r[py] = 1;
51                     father[px] = py;
52                     sum+=q[i].c;
53                 }
54             }
55             else
56             {
57                 if(!r[px])
58                 {
59                     sum+=q[i].c;
60                     r[px] = 1;
61                 }
62             }
63         }
64         printf("%d\n",sum);
65     }
66     return 0;
67 }