題目：
Problem Description
In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. The maximal pseudoforests of G are the pseudoforest subgraphs of G that are not contained within any larger pseudoforest of G. A pesudoforest is larger than another if and only if the total value of the edges is greater than another one’s.
Input
The input consists of multiple test cases. The first line of each test case contains two integers, n(0 < n <= 10000), m(0 <= m <= 100000), which are the number of the vertexes and the number of the edges. The next m lines, each line consists of three integers, u, v, c, which means there is an edge with value c (0 < c <= 10000) between u and v. You can assume that there are no loop and no multiple edges.
The last test case is followed by a line containing two zeros, which means the end of the input.
Output
Output the sum of the value of the edges of the maximum pesudoforest.
Sample Input
3 3
0 1 1
1 2 1
2 0 1
4 5
0 1 1
1 2 1
2 3 1
3 0 1
0 2 2
0 0
Sample Output
3
5
Source
“光庭杯”第五屆華中北區程序設計邀請賽 暨 WHU第八屆程序設計競賽
分析與總結：
這題題意理解了好一陣子才明白, 給出一個圖，要求出最大的pseudoforest， 所謂pseudoforest就是指這個圖的一個子圖，這個子圖的每個連通分量中最多只能有一個環， 而且這個子圖的所有權值之和最大。這個就是所謂的偽森林。
過程類似與kruskal求最小生成樹，千萬不要直接求最大生成樹，一開始時我想到的方法是用kruskal算法求出這個圖的最大生成樹， 然後給每一棵數再加上一條最大的邊，構成一個環。 但是WA得快吐血了。
正確的做法和求最大生成樹很類似，但是有一點改變， 因為每個連通分量允許有一個回環， 所以，我們可以在進行合並兩顆樹時，要判斷這兩顆樹是否有回環，如果兩個樹都有回環，那麼明顯不可以合並這兩顆樹， 如果只有一棵樹有回環，那麼可以合並，然後標上記號。如果兩個都沒有回環，那麼就直接合並了。
如果有兩個點是屬於同一棵樹上的，那麼判斷這棵樹上是否已有回環，如果沒有的話，那麼允許有一個回環，可以鏈接這兩點，再標上記號。
具體看代碼。
代碼：
[cpp]
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 10005
using namespace std;
struct Edge{
int u,v,val;
friend bool operator<(const Edge&a,const Edge&b){
return a.val>b.val;
}
}arr[N*10];
int f[N],rank[N],vis[N],n,m;
void init(){
for(int i=0; i<=n; ++i)
f[i]=i, rank[i]=0;
}
int find(int x){
int i,j=x;
while(j!=f[j]) j=f[j];
while(x!=j){ i=f[x]; f[x]=j; x=i; }
return j;
}
void Union(int x,int y){
int a=find(x),b=find(y);
if(a==b) return ;
if(rank[a]>rank[b])
f[b]=a;
else{
if(rank[a]==rank[b])
++rank[b];
f[a]=b;
}
}
int main(){
while(~scanf("%d%d",&n,&m)){
if(!n&&!m)break;
for(int i=0; i<m; ++i)
scanf("%d%d%d",&arr[i].u,&arr[i].v,&arr[i].val);
init();
sort(arr,arr+m);
memset(vis, 0, sizeof(vis));
long long ans=0;
for(int i=0; i<m; ++i){
int a=find(arr[i].u), b=find(arr[i].v);
if(a!=b){
if(vis[a]&&vis[b]) continue;//兩個都有環了
if(vis[a]||vis[b]) vis[a]=vis[b]=1;
ans += arr[i].val;
Union(a,b);
}
else if(!vis[a]){ // 雖然是同一棵數，但是還沒有環
Union(a,b);
vis[a] = 1;
ans+=arr[i].val;
}
}
printf("%lld\n", ans);
}
return 0;
}
