专栏首页算法修养HDU 3367 Pseudoforest(Kruskal)

HDU 3367 Pseudoforest(Kruskal)

Pseudoforest

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 2382    Accepted Submission(s): 933

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求出一个最大的子图(子图的每个连通分量最多有一个环) 用kruskal算法求出最大生成树  不过要判断是否有环  2树合并时 :若2个子树都有环不能合并 只有一个有环可以合并 但合并后的树有环 若2个子树都没环直接合并
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <stdio.h>

using namespace std;
#define MAX 10000
int n,m;
struct Node
{
	int x;
	int y;
	int w;
}a[MAX*10+5];
int father[MAX+5];
bool tag[MAX+5];
int cmp(Node a,Node b)
{
	return a.w>b.w;
}
int find(int x)
{
	if(x!=father[x])
		father[x]=find(father[x]);
	return father[x];
}
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		if(n==0&&m==0)
			break;
		for(int i=0;i<m;i++)
			scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);
		for(int i=0;i<n;i++)
		{
			father[i]=i;
			tag[i]=false;
		}
		sort(a,a+m,cmp);
		int ans=0;
		for(int i=0;i<m;i++)
		{
             int xx=find(a[i].x);
			 int yy=find(a[i].y);
			 if(xx!=yy)
			 {
				 if(tag[xx]&&tag[yy])
					 continue;
				 ans+=a[i].w;
				 father[xx]=yy;
				 if(tag[xx]||tag[yy])
				 {tag[xx]=true;tag[yy]=true;}
			 }
			 else
			 {
				 if(tag[xx]||tag[yy])
					 continue;
				 ans+=a[i].w;
				 tag[xx]=true;tag[yy]=true;
			 }
		}
		printf("%d\n",ans);
	}
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • POJ--1690 (Your)((Term)((Project)))(字符串处理)

    (Your)((Term)((Project))) Time Limit: 1000MS Memory Limit: 10000K Total...

    ShenduCC
  • ZOJ 3326 An Awful Problem(模拟)

    An Awful Problem ---- Time Limit: 1 Second      Memory Limit: 32768 KB ---- In o...

    ShenduCC
  • ZOJ 3204 Connect them

    Connect them ---- Time Limit: 1 Second      Memory Limit: 32768 KB ---- You have...

    ShenduCC
  • POJ--1690 (Your)((Term)((Project)))(字符串处理)

    (Your)((Term)((Project))) Time Limit: 1000MS Memory Limit: 10000K Total...

    ShenduCC
  • POJ 2260(ZOJ 1949) Error Correction 一个水题

    A boolean matrix has the parity property when each row and each column has an ev...

    谙忆
  • BZOJ 3053: The Closest M Points(K-D Tree)

    attack
  • POJ 3662 Telephone Lines【Dijkstra最短路+二分求解】

    Telephone Lines Time Limit: 1000MS Memory Limit: 65536K Total Submission...

    Angel_Kitty
  • 数据结构(一)

    广度优先搜索(BFS)的一个常见应用是找出从根结点到目标结点的最短路径。 用队列实现BFS的模板

    wsuo
  • CF--思维练习--CodeForces - 219C Color Stripe (思维)

    ACM思维题训练集合 A colored stripe is represented by a horizontal row of n square cell...

    风骨散人Chiam
  • POJ--1936 All in All(水题,暴力即可)

    All in All Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 3...

    ShenduCC

扫码关注云+社区

领取腾讯云代金券