Pseudoforest

/*初级想方法，最大生成树再加一条最长边讲解：没看明白题意的傻逼想法，题目说不是最大生成树，森林也可以，但是最多只能有一个环正解：将所有的边都加到树上，加的时候如果两点在同一个并查集：如果原来有环就不能加如果不在同一个并查集：如果原来两个都有环不能加*/#include<bits/stdc++.h>using namespace std;struct node{    int u,v,val;    node()    {}    node(int a,int b,int c)    {        u=a;        v=b;        val=c;    }    bool operator < (const node &a) const    {        return val>a.val;    }};vector<node>edge;int bin[10005];int n,m;int x,y,val;int h[10005];//表示当前集合有没有环long long cur=0;void init(){    for(int i=0;i<=n;i++)    {        bin[i]=i;        h[i]=0;    }    edge.clear();    cur=0;}int findx(int x){    int temp=x;    while(x!=bin[x])        x=bin[x];    bin[temp]=x;    return x;}int main(){    //freopen("C:\\Users\\acer\\Desktop\\in.txt","r",stdin);    while(scanf("%d%d",&n,&m)!=EOF&&(n||m))    {        init();        for(int i=0;i<m;i++)        {            scanf("%d%d%d",&x,&y,&val);            edge.push_back(node(x,y,val));        }        sort(edge.begin(),edge.end());        for(int i=0;i<edge.size();i++)        {            int fx=findx(edge[i].u);            int fy=findx(edge[i].v);            if(fx==fy)//两个原来就是一个并查集的就可能产生环了            {                if(h[fx])//有环了                    continue;                cur+=edge[i].val;                h[fx]=1;            }            else            {                if(h[fx]&&h[fy])//两个集合都有环不可以                    continue;                bin[fy]=fx;                cur+=edge[i].val;                if(h[fx]||h[fy])                    h[fx]=1;            }        }        printf("%lld\n",cur);    }    return 0;}