Pseudoforest
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1790 Accepted Submission(s): 687
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.
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.
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
/*
HODJ 3367 最小生成树K,判断有无环的出现
*/
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
struct node{
int x,y,dis;
};
node e[100001];
int pre[10001],circle[10001];
int cmp(node a,node b)
{
return a.dis>b.dis;
}
int find(int x)
{
if(x!=pre[x])
return pre[x]=find(pre[x]);
return pre[x];
}
int main()
{
int n,m,i,j,sum,x,y,a,b,v;
// freopen("test.txt","r",stdin);
while(scanf("%d%d",&n,&m))
{
if(n==0&&m==0) break;
for(i=0;i<n;i++)// 注意题目是从0开始的
pre[i]=i;
memset(circle,0,sizeof(circle));
for(i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&v);
e[i].x=a;
e[i].y=b;
e[i].dis=v;
}
sort(e,e+m,cmp);
sum=0;
for(i=0;i<m;i++)
{
x=find(e[i].x);
y=find(e[i].y);
if(x!=y)
{
if(!circle[x]&&!circle[y])//两个都不是环
{
sum+=e[i].dis;
pre[x]=y;
}
else if(!circle[x]||!circle[y])//其中有一个是环，合并后两个都是环
{
pre[x]=y;
sum+=e[i].dis;
circle[x]=circle[y]=1;
}
}
else// x==y表示两个是一个集合里的，有相同的根
//如果x还没构成环，现在又多条路径，构成环
//因为e[i].x，e[i].y是一条路径，现在又有相同的根x，构成环
{
if(!circle[x])//！circle[y]一样，x==y
{
circle[x]=1;
sum+=e[i].dis;
}
}
}
printf("%d\n",sum);
}
return 0;
}