hdu 3367 Pseudoforest 最大生成树

传送门：Pseudoforest

题目大意

就是求最大生成树，但是前提是要组成一个环

解题思路

按照边的最大到小排序一下，当变为一个环的时候就是要求的最大生成树，当然肯定不是当变为一个环就退出，当变为两个环的时候就不加这个边了，直到结束！

AC代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 100005;
int pre[MAXN],vis[MAXN];
int N,M;

struct Node{
int a,b,val;
}s[MAXN];

void init()
{
for(int i=0;i<=N;i++)
        pre[i] = i;
}
bool cmp(Node a,Node b)
{
return a.val>b.val;
}
int find(int x)
{
return (x == pre[x]) ? pre[x] : (pre[x] = find(pre[x]));
}

int main()
{
int a,b,c;
while(~scanf("%d%d",&N,&M))
    {
if(M==0 && N==0) break;
memset(vis,0,sizeof vis);
        init();
for(int i=0;i<M;i++)
scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].val);
        sort(s,s+M,cmp);
int sum = 0;
bool flag = false;
for(int i=0;i<M;i++)
        {
int fx = find(s[i].a),fy = find(s[i].b);
if(fx != fy)
            {
if(vis[fx] && vis[fy]) continue;
if(vis[fx] || vis[fy]) vis[fx] = 1,vis[fy] = 1;
                pre[fx] = fy;
                sum += s[i].val;
            }
else if(!vis[fx])
            {
                vis[fx] = 1;
                sum+=s[i].val;
            }
        }
printf("%d\n",sum);
    }
return 0;
}