当前位置：网站首页>Minimum spanning tree -- unblocked project hdu1863

Minimum spanning tree -- unblocked project hdu1863

2022-04-23 05:08:00 【FOWng_ lp】

Insert picture description here

Sample Input
3 3
1 2 1
1 3 2
2 3 4
1 3
2 3 2
0 100

Sample Output
3
?

Topic link 

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
typedef long long LL;
LL ans,t;
int fa[105];
struct N{
    
	int a,b,c;
	};
bool cmp(N a, N b){
    
	return a.c < b.c;
	}
int find(int x){
    
		if(x!=fa[x]) return find(fa[x]);
		else return x;
		}
void combine(int a,int b){
    
	if(find(a)!=find(b))fa[find(a)] = find(b);
	}
int main(){
    
	int n,m;
	N A[105];
	while(cin >> n >> m){
    
		if(!n)break;
		ans=0,t=1;
		for(int i = 1;i <= m;i++)fa[i]=i;
		for(int i = 1;i <= n;i++){
    
			cin >> A[i].a >> A[i].b >>A[i].c;
			}
		sort(A+1,A+1+n,cmp);
		for(int i = 1;i <= n;i++){
    
			if(find(A[i].a)!=find(A[i].b)){
    
				combine(A[i].a,A[i].b);
				ans+=A[i].c;
				}
			}
		for(int i = 2;i <= m;i++){
    
			if(find(i)!=find(i-1)){
    
				t=0;
				break;
				}
			}
		if(t)cout <<ans <<endl;
		else cout << "?" <<endl;
		}
	return 0;
	}

版权声明
本文为[FOWng_ lp]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/04/202204220549345393.html

边栏推荐

猜你喜欢

随机推荐