90分求助,第二个点为什么会WA
查看原帖
90分求助,第二个点为什么会WA
684890
Rhss楼主2022/10/10 12:28
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m;
ll father[2002];
void init() {
	for (int i = 1; i <= n; ++i) {
		father[i] = i;
	}
}
ll findfather(ll x) {
	if (x == father[x]) {
		return x;
	}
	return father[x] = findfather(father[x]);
}
void merge(ll a, ll b) {
	int fa = findfather(a);
	int fb = findfather(b);
	if (fa != fb) {
		father[fa] = fb;
	}
}
struct node {
	ll l, r, cost;
} t[10004];
bool cmp(node a, node b) {
	return a.cost < b.cost;
}
int main(){
	cin>>n>>m;
	init();
	for(ll i = 1;i<=m;++i){
		cin>>t[i].l>>t[i].r>>t[i].cost;
	}
	sort(t+1,t+m+1,cmp);
	ll ans = 0;
	ll size = 0;
	for(ll i = 1;i<=m;++i){
		if(findfather(t[i].l)!=findfather(t[i].r)){
			merge(t[i].l,t[i].r);
			ans = max(ans,t[i].cost);
			size++;
		}
		if(size==m-1){
			break;
		}
	}
	cout<<ans;
	return 0;
}
2022/10/10 12:28
加载中...