HDU 3367 最大生成树

【copy的讨论版】
这题题意理解了好一阵子才明白,  给出一个图，要求出最大的pseudoforest， 所谓pseudoforest就是指这个图的一个子图，这个子图的每个连通分量中最多只能有一个环， 而且这个子图的所有权值之和最大。这个就是所谓的伪森林。

过程类似与kruskal求最小生成树，千万不要直接求最大生成树，一开始时我想到的方法是用kruskal算法求出这个图的最大生成树， 然后给每一棵数再加上一条最大的边，构成一个环。 但是WA得快吐血了。

正确的做法和求最大生成树很类似，但是有一点改变， 因为每个连通分量允许有一个回环， 所以，我们可以在进行合并两颗树时，要判断这两颗树是否有回环，如果两个树都有回环，那么明显不可以合并这两颗树， 如果只有一棵树有回环，那么可以合并，然后标上记号。如果两个都没有回环，那么就直接合并了。

如果有两个点是属于同一棵树上的，那么判断这棵树上是否已有回环，如果没有的话，那么允许有一个回环，可以链接这两点，再标上记号。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<functional>
#include<vector>

using namespace std;
const int maxn = 10005;
const int maxm = 100005;
typedef long long ll;
int n,m;
struct edge{
    int u,v,cost;
    bool operator < (const edge &z) const{
        return z.cost < cost;
    }
}ed[maxm];

int par[maxn];
int rnk[maxn];
int loop[maxn];

void init_union(){
    memset(par,-1,sizeof(par));
    memset(rnk,0,sizeof(rnk));
    memset(loop,0,sizeof(loop));
}
int find(int x){
    while(par[x] >= 0) x = par[x];
    return x;
}
void unite(int x,int y){
    x = find(x);y = find(y);
    if(x == y) return;
    if(rnk[x] < rnk[y]){
        par[x] = y;
        loop[y] += loop[x];
    }else{
        par[y] = x;
        loop[x] += loop[y];
        if(rnk[x] == rnk[y]) rnk[x]++;
    }
}
bool same(int x,int y){
    return find(x) == find(y);
}

void solve(){
    sort(ed,ed+m);
    init_union();
    ll ans = 0;
    for(int i=0;i<m;i++){
        if(!same(ed[i].u,ed[i].v)){
            if(loop[find(ed[i].u)] + loop[find(ed[i].v)] == 2) continue;
            ans += ed[i].cost;
            unite(ed[i].u,ed[i].v);
        }else{
            int fa = find(ed[i].u);
            if(!loop[fa]){
                loop[fa] = 1;
                ans += ed[i].cost;
            }
        }
    }
    printf("%lld\n",ans);
}

int main(){
    while(~scanf("%d%d",&n,&m)){
        if(n == 0 && m == 0) break;
        for(int i=0;i<m;i++){
            scanf("%d%d%d",&ed[i].u,&ed[i].v,&ed[i].cost);
        }
        solve();
    }

    return 0;
}