HDOJ 題目3367 Pseudoforest（并查集）
來源：程序員人生 發布時間：2015-07-29 08:17:27 閱讀次數：3283次
Pseudoforest
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1932 Accepted Submission(s): 746
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
Source
“光庭杯”第5屆華中北區程序設計約請賽
暨 WHU第8屆程序設計比賽
Recommend
lcy | We have carefully selected several similar problems for you: 3362 3368 3365 3369 3366
題意：求出1個最大的子圖（子圖的每一個連通份量最多有1個環）
用kruskal算法求出最大生成樹 不過要判斷是不是有環 2樹合并時 ：若2個子樹都有環不能合并 只有1個有環可以合并 但合并后的樹有環 若2個子樹都沒環直接合并
ac代碼
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int pre[10010],vis[10010];
struct s
{
int u,v,w;
}edge[100100];
int n,m;
int cmp(const void *a,const void *b)
{
return (*(struct s *)b).w-(*(struct s *)a).w;
}
void init()
{
int i;
for(i=0;i<=n;i++)
pre[i]=i;
}
int find(int x)
{
if(x==pre[x])
return x;
return pre[x]=find(pre[x]);
}
int merge(int u,int v)
{
int fu=find(u);
int fv=find(v);
if(fu==fv)
{
if(!vis[fu])
{
vis[fu]=1;
return 1;
}
return 0;
}
if(vis[fu]&&vis[fv])
return 0;
if(vis[fu])
pre[fv]=fu;
else
pre[fu]=fv;
return 1;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF,n||m)
{
int i;
init();
for(i=0;i<m;i++)
{
int u,v,w;
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
}
qsort(edge,m,sizeof(edge[0]),cmp);
int ans=0;
memset(vis,0,sizeof(vis));
for(i=0;i<m;i++)
{
int u=edge[i].u;
int v=edge[i].v;
int w=edge[i].w;
if(merge(u,v))
ans+=w;
}
printf("%d
",ans);
}
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
