Pseudoforest

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

3

5

题意：这题的题意折腾了好久才懂，開始以为是求最多有一个环的最大联通分量，然后WA了，后来才知道是求多个分量的最大和。每一个分量最多有一个环。

题解：边权从大到小排序，对于每条边的起点终点a、b有三种情况：

1、a、b分属两个环。此时a、b不能连接；

2、a、b当中一个属于环。此时将还有一个连过去或者两个都不在环中，此时随意连；

3、a、b在同一集合。但该集合无环。此时连接a、b并生成环。

#include <stdio.h>

#include <string.h>

#include <algorithm>

#define maxn 10002

#define maxm 100002

using std::sort;

struct Node{

	int u, v, cost;

} E[maxm];

int pre[maxn];

bool Ring[maxn];

bool cmp(Node a, Node b){

	return a.cost > b.cost;

}

int ufind(int k)

{

	int a = k, b;

	while(pre[k] != -1) k = pre[k];

	while(a != k){

		b = pre[a];

		pre[a] = k;

		a = b;

	}

	return k;

}

int greedy(int n, int m)

{

	int ans = 0, i, u, v;

	for(i = 0; i < m; ++i){

		u = E[i].u; v = E[i].v;

		u = ufind(u); v = ufind(v);

		if(Ring[u] && Ring[v]) continue;

		if(u != v){

			if(Ring[v]) pre[u] = v;

			else pre[v] = u;

			ans += E[i].cost;

		}else if(Ring[v] == false){

			Ring[v] = true;

			ans += E[i].cost;

		}

	}

	return ans;

}

int main()

{

	int n, m, a, b, c, i;

	while(scanf("%d%d", &n, &m), n||m){

		memset(pre, -1, sizeof(pre));

		memset(Ring, 0, sizeof(Ring));

		for(i = 0; i < m; ++i)

			scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].cost);

		sort(E, E + m, cmp);

		printf("%d\n", greedy(n, m));

	}

	return 0;

}