hdu3367Pseudoforest kruskal求最大生成树

//给一个图，问其边长之和最大伪森林
//刚开始的想法是在这个图的每一个连通子块找其最大生成树
//然后在这个子块中找一条不在这个树上加上去，这种想法是错误的，因为可能存在
//一个子块可能本来有两个环，但是删除一条小的边使得它成为两个子块比将这个子块删除一个环的边权和大
//正确的贪心策略是尽可能的找长的边，如果要合并的两颗子树中都有环就不合并，如果只有一个有环
//依然合并，需要将其标记为有环，如果所要加的边的两个点在一颗树上也要标记有环
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn = 10010 ;
const int maxm = 100010 ;
const int inf = 0x3f3f3f3f ;
int flag[maxn] ;
int F[maxn] ;
int n , m ;
struct node
{
int u , v , w ;
bool operator < (const struct node tmp)const
    {
return tmp.w < w ;
    }
}edge[maxm] ;
int find(int x)
{
if(x == F[x])return F[x] ;
return F[x] = find(F[x]) ;
}
void kruskal()
{
int ans = 0 ;
for(int i = 1;i <= m;i++)
    {
int fu = find(edge[i].u);
int fv = find(edge[i].v);
if(flag[fv] && flag[fu])
continue  ;
        ans += edge[i].w ;
        F[fv] = fu ;
if(flag[fv] || flag[fu] || fv == fu)
        flag[fu] = 1 ;
    }
cout<<ans<<endl;
}
int main()
{
//freopen("in.txt" , "r" ,stdin) ;
while(scanf("%d%d" , &n , &m) && (n + m))
    {
memset(flag , 0 , sizeof(flag)) ;
for(int i = 0;i <= n;i++)
        F[i] = i ;
for(int i = 1;i <= m;i++)
scanf("%d%d%d" , &edge[i].u , &edge[i].v , &edge[i].w) ;
        sort(edge + 1, edge + 1  + m) ;
        kruskal();
    }
return 0 ;
}