hdu 3367 Pseudoforest（最大生成樹）

/*  可以說是一個最大生成樹的問題吧，

    題意：求出一個最大的子圖（子圖的每個連通分量最多有一個環）

   用kruskal算法求出最大生成樹  不過要判斷是否有環  2樹合並時 ：若2個子樹都有環不能合並 只有一個有環可以合並 但合並後的樹有環 若2個子樹都沒環直接合並

*/

#include<cstdio>

#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
struct Edge
{
    int u,v,d;
    bool operator < (const Edge &s) const
    {
        return d>s.d;
    }
}a[100010];
int p[10010],vis[10010];
int find(int x)
{
    return p[x]==x?x:p[x]=find(p[x]);
}
int Union(int x,int y)
{
    if(x==y) return 0;
    p[x] = y;
}
int main()
{
    while(scanf("%d%d",&n,&m)==2)
    {
        if(!n&&!m) break;
        memset(vis,0,sizeof(vis));
        for(int i = 0; i <= n; i++) p[i]=i;
        for(int i = 0; i < m; i++)
        scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].d);
        sort(a,a+m);
        long long ans=0;
        for(int i = 0; i < m; i++)
        {
            int x = find(a[i].u);
            int y = find(a[i].v);
            if(x!=y)
            {
                if(vis[x]&&vis[y]) continue;
                if(vis[x]||vis[y])
                vis[x]=vis[y]=1;
                ans+=a[i].d;
                Union(x,y);
            }
            else if(!vis[x])
            {
                vis[x] = 1;
                ans+=a[i].d;
                Union(x,y);
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}