最小生成树0分求助
查看原帖
最小生成树0分求助
1268524
DX3906_ourstar楼主2024/10/15 13:42

rt

#include<iostream>
#include<algorithm>
#define re register
#define int long long
using namespace std;

const int N = 1e6 + 5;

int a,b,cnt,ans;
int fa[N];

struct edge{
	int u,v,w;
}e[N];

inline int find(int x){
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

inline bool cmp(edge a,edge b){
	return a.w < b.w;
}

inline void add(int u,int v,int w){
	cnt ++;
	e[cnt].u = u;
	e[cnt].v = v;
	e[cnt].w = w;
	return ;
}

inline void cs(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	for(re int i = 1;i <= N;i ++){
		fa[i] = i;
	}
	return ;
}

signed main(){
	cs();
	cin>>a>>b;
	add(1,2,a);
	add(2,3,b);
	sort(e + 1,e + 3,cmp);
	for(re int i = 1;i <= 2;i ++){
		int x = find(e[i].u);
		int y = find(e[i].v);
		if(x != y){
			ans += e[i].w;
			fa[x] = y;
		}
	}
	cout<<ans<<"\n";
	return 0;
}
2024/10/15 13:42
加载中...