首页 > 代码库 > hdu 3367 Pseudoforest (最小生成树)
hdu 3367 Pseudoforest (最小生成树)
Pseudoforest
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1526 Accepted Submission(s): 580
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.
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第八届程序设计竞赛
Recommend
lcy | We have carefully selected several similar problems for you: 3362 3368 3364 3365 3369
伪森林:
题意为有一个伪森林,即森林里的每棵树最多有一个环。
这题还算是不错的,最小生成树小变形,要用kruskal算法,边的排序要按值大到小排。
排完序后就可以按kruskal的做法做了,不过要多作一个circle[]数组来记录每棵树环的情况,如果该树有一个环了就不能再加环,并且如果一条边有两个点一个属于有环树,一个不属于有环树,那么并查集并的时候要讲第二个点并到第一个点中,这样可以避免多个环的情况。思路清晰后还是挺简单的。
1 //546MS 1464K 1096 B G++ 2 #include<stdio.h> 3 #include<string.h> 4 #include<stdlib.h> 5 #define N 10005 6 struct node{ 7 int u,v,d; 8 }p[10*N]; 9 int set[N]; 10 int circle[N]; 11 int n,m; 12 int cmp(const void*a,const void*b) 13 { 14 return (*(node*)b).d-(*(node*)a).d; 15 } 16 int find(int x) 17 { 18 if(set[x]!=x) set[x]=find(set[x]); 19 return set[x]; 20 } 21 int kruskal() 22 { 23 int ans=0; 24 for(int i=0;i<m;i++){ 25 int tu=find(p[i].u); 26 int tv=find(p[i].v); 27 if(tu==tv){ 28 if(!circle[tu]){ 29 circle[tu]=1; 30 ans+=p[i].d; 31 } 32 continue; 33 } 34 if(circle[tu] && circle[tv]) continue; 35 if(circle[tu]) set[tv]=tu; 36 else set[tu]=tv; 37 ans+=p[i].d; 38 } 39 return ans; 40 } 41 int main(void) 42 { 43 while(scanf("%d%d",&n,&m)!=EOF&&(n+m)) 44 { 45 for(int i=0;i<=n;i++) set[i]=i; 46 memset(circle,0,sizeof(circle)); 47 for(int i=0;i<m;i++){ 48 scanf("%d%d%d",&p[i].u,&p[i].v,&p[i].d); 49 } 50 qsort(p,m,sizeof(p[0]),cmp); 51 printf("%d\n",kruskal()); 52 } 53 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。