题解 | #畅通工程#

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN = 101;
int father[MAXN];
int height[MAXN];
struct Edge{
	int m1, m2;
	int value;
};
bool comp(Edge rhs, Edge lhs){
	return rhs.value < lhs.value;
}
void Initial(int n){
	for (int i = 0; i <= n; i++){
		father[i] = i;
		height[i] = 0;
	}
}
int Find(int x){
	if (x != father[x]){
		father[x] = Find(father[x]);
	}
	return father[x];
}
void Union(int x, int y){
	x = Find(x);
	y = Find(y);
	if (x != y){
		if (height[x] < height[y]){
			father[x] = y;
		}
		else if (height[y] < height[x]){
			father[y] = x;
		}
		else{
			father[y] = x;
			height[x]++;
		}
	}
	return;
}
int main(){
	int n, m;
	while (scanf("%d%d", &n,&m) != EOF){
		if (n == 0){
			break;
		}
		Initial(m);
		int answer = 0;
		Edge edge[101];
		for (int i = 0; i < n; i++){
			scanf("%d%d%d", &edge[i].m1, &edge[i].m2, &edge[i].value);
		}
		sort(edge, edge + n, comp);
		for (int i = 0; i < n; i++){
			if (Find(edge[i].m1) != Find(edge[i].m2)){
				answer += edge[i].value;
				Union(edge[i].m1, edge[i].m2);
			}
		}
		int i = 2;
		for (; i <= m; i++){
			if (Find(i) != Find(1)){
				printf("?\n");
				break;
			}
		}
		if (i == m+1){
			printf("%d\n", answer);
		}
	}
}