默写模板,不知道哪里错了
查看原帖
默写模板,不知道哪里错了
705229
mayijian楼主2023/10/18 18:42

rt

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
int f[maxn], n, m;
struct nd{
	int x, y, val;
}a[maxn];
int find(int x){
	while(x!=f[x]) x=f[x]=f[f[x]];
	return x;
}
bool cmp(nd a, nd b){
	return a.val<b.val;
}
void merge(int x, int y){
	f[find(x)] = find(y);
}

bool check(int x, int y){
	return (find(x)==find(y));
	
}

int main(){
	cin>>n>>m;
	for(int i=1; i<=n; i++) f[i] = i;
	for(int i=1; i<=m; i++){
		int x, y, z;
		cin>>x>>y>>z;
		a[i].x=x, a[i].y=y, a[i].val=z;
	}
	sort(a+1, a+1+m, cmp);
	int cnt=0, ans=0;
	for(int i=1; i<=m; i++){
		if(check(a[i].x, a[i].y)) continue;
		ans+=a[i].val;
		merge(a[i].x, a[i].y);
		if(++cnt = n-1){
			break;
		}
	}
	if(cnt != n-1) cout<<"orz";
	else cout<<ans;
//	for(int i=1;i<=m;i++){
//		cout<<a[i].x<<" "<<a[i].y<<" "<<a[i].val<<endl;
//		cout<<f[i];
	}
}
2023/10/18 18:42
加载中...