首页 > 代码库 > HDU 3367 Pseudoforest

HDU 3367 Pseudoforest

2024-10-31 04:15:02   208人阅读

https://vjudge.net/problem/HDU-3367

题意：

一个伪森林是一个每个连通分量至多有一个环的无向图，给出一个图，图中不包含重边和圈，请你求出这个图的权值最大的伪森林。

思路：

一开始想的是用最大生成树，然后加一条最大的不在生成树中的边，wa了，真是可笑题意都没有理解清楚。题中的图可以是非连通的。

之后看了题解，发现是用并查集的思路，先把边从大到小进行排序，之后对于每一条边，我们看它的两个点a，b。

有2大的种情况：

1.a，b在一个连通分量中，并且他们没有被标记，则把这条边加入进去，并且把a，b标记上，说明它在环中。

2.a，b不在同一个连通分量中：

则，如果他们所在的连通分量都是环，那么这条边就不可以加，因为加上这个图的这个连通分量就有两个环了，不符合题意；

如果有一个点在环中，那么加上这条边还是只有一个环，可以加，然后把这个点以及他们所合并的整个连通分量都标记为有环；

如果两个点都不在环中，那么直接合并就可以了。

一开始我被如何判断环给迷惑了，用了诸如拓扑排序的思想和有环图的边的数量大于等于点的数量等方法，结果都不对，无奈只能去看题解。

其实方法很简单，当我发现两个点在同一个连通分量中的时候，这两个点就没有标记，那么加上这条边成环，把两个点直接标记就行了，没有那么复杂。

 

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <algorithm>
  4 #include <vector>
  5 using namespace std;
  6 
  7 struct edge
  8 {
  9     int x,y,c;
 10 }e[100005];
 11 
 12 int par[10005];
 13 bool v[10005];
 14 
 15 void init(int n)
 16 {
 17     for (int i = 0;i < n;i++)
 18         par[i] = i;
 19 }
 20 
 21 int fin(int x)
 22 {
 23     if (x == par[x]) return x;
 24     else return par[x] = fin(par[x]);
 25 }
 26 
 27 void unit(int x,int y)
 28 {
 29     x = fin(x);
 30     y = fin(y);
 31 
 32     if (x != y) par[x] = y;
 33 }
 34 
 35 bool cmp(edge aa,edge bb)
 36 {
 37     return aa.c > bb.c;
 38 }
 39 
 40 int main()
 41 {
 42     int n,m;
 43 
 44     while (scanf("%d%d",&n,&m) == 2)
 45     {
 46         if (m == 0 && n == 0) break;
 47 
 48         init(n);
 49 
 50         memset(v,0,sizeof(v));
 51 
 52         for (int i = 0;i < m;i++)
 53         {
 54             scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].c);
 55         }
 56 
 57         sort(e,e+m,cmp);
 58 
 59         int ans = 0;
 60 
 61         for (int i = 0;i < m;i++)
 62         {
 63             int x = e[i].x,y = e[i].y;
 64 
 65             if (fin(x) == fin(y))
 66             {
 67                 if (!v[fin(x)])
 68                 {
 69                     ans += e[i].c;
 70                     v[x] = v[y] = 1;
 71                     v[fin(x)] = 1;
 72                 }
 73             }
 74             else
 75             {
 76                 if (v[fin(x)] && v[fin(y)])
 77                 {
 78                     ;
 79                 }
 80                 else if (!v[fin(x)] && !v[fin(y)])
 81                 {
 82                     unit(x,y);
 83 
 84                     ans += e[i].c;
 85                 }
 86                 else
 87                 {
 88                     ans += e[i].c;
 89 
 90                     v[fin(y)] = v[fin(x)] = v[x] = v[y] = 1;
 91 
 92                     unit(x,y);
 93                 }
 94             }
 95         }
 96 
 97         printf("%d\n",ans);
 98     }
 99 
100     return 0;
101 }

 

HDU 3367 Pseudoforest


联系
我们