Problem H
Time Limit : 10000/5000ms (Java/Other) Memory Limit :65536/65536K (Java/Other)
Total Submission(s) : 1 Accepted Submission(s) : 1
Problem Description
In graph theory, apseudoforest is an undirected graph in which every connected component has atmost one cycle. The maximal pseudoforests of G are the pseudoforest subgraphsof G that are not contained within any larger pseudoforest of G. A pesudoforestis larger than another if and only if the total value of the edges is greaterthan another one’s.<br><br>
Input
The input consists of multipletest 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 vertexesand the number of the edges. The next m lines, each line consists of threeintegers, 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 multipleedges.<br>The last test case is followed by a line containing two zeros,which means the end of the input.<br>
Output
Output the sum of the value ofthe edges of the maximum pesudoforest.<br>
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
算法分析：
题意：
这是百度上的题意：在图论中，如果一个森林中有很多连通分量，并且每个连通分量中至多有一个环，那么这个森林就称为伪森林。现在给出一个森林，求森林包含的最大的伪森林，其大小通过所有边的权值之和来比较。
我的理解就是：求一个环的最大生成树。
kruskal变形：
1. 从大到小排序
2. 合并时，如果会生成两个环，则不合并，需要数组标记。
1）如果是两棵树在进行合并操作
两棵树都有环，不能进行合并操作。
如果只有一个数有环，可以进行合并操作。合并前先做一下标记。
如果都没有环，可以进行合并操作。
2）如果是是同一颗树在进行合并操作。
那么这棵树合并前必然不能有环。
代码实现：
#include<bits/stdc++.h>
using namespace std;
int fa[10010];
bool vis[10010];
struct node
{
int x,y,v;
}a[100005];
int find(int x)
{
return x==fa[x]?x:fa[x]=find(fa[x]);
}
int cmp(node b,node c)//这里要从大到小排序
{
return b.v>c.v;
}
int main()
{
int n,m;
while( scanf("%d%d",&n,&m)!=EOF&&(n||m))
{
int num=0;
for(int i=0;i<=n;i++)
fa[i]=i;
memset(vis,0,sizeof(vis));
for(int i=1;i<=m;i++)
{
int x,y,v;
scanf("%d%d%d",&x,&y,&v);
a[num].x=x;
a[num].y=y;
a[num].v=v;
num++;
}
sort(a,a+num,cmp);
int ans=0;
for(int i=0;i<num;i++)
{
int r1=find(a[i].x);
int r2=find(a[i].y);
if(r1!=r2)//表示两棵树
{
if(vis[r1]==1&&vis[r2]==1)//如果两棵树都有环，则不能合并
continue;
if(vis[r1]||vis[r2])//如果其中有一个有环，合并
{
vis[r1]=vis[r2]=1;//标记有环
}
fa[r1]=r2;
ans+=a[i].v;
}
else if(!vis[r1])//如果在一棵树内，且没有环
{
//不能进行合并操作，不然会产生环，加上权值即可
ans+=a[i].v;
vis[r1]=1;
}
}
printf("%d\n",ans);
}
return 0;
}