最小生成树

题目传送门

大致思路

将边按权重升序排序,然后根据边两边的节点是否连通判断是否将该边加入(用到并查集)

Code

int father[5721];
int find(int x){
	if(x!=father[x]) father[x]=find(father[x]);
	return father[x];
}
bool uoionset(int a,int b){
	a=find(a);
	b=find(b);
	if(a!=b) {
		father[a]=b;
		return true;
	}
	return false;
}


bool cmp(vector<int> &a,vector<int> &b){
	return a.back() <  b.back();
}

void solve() {
	int n,m;
	cin >> n >> m;
	vector<vector<int>> a(m+1);
	for(int i=1;i<=n;i++) father[i]=i;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin >> u >>v >>w;
		a[i]={u,v,w};
	}
	sort(a.begin()+1,a.end(),cmp);
	int ans=0;
	int cnt=0;
	for(int i=1;i<=m;i++){
		int u=a[i][0],v=a[i][1],w=a[i][2];
		if(uoionset(u,v)) {
			ans+=w;
			cnt++;
			if(cnt==n-1) break;
		}
	}
	if(cnt!=n-1) cout << "orz" <<el;
	else cout << ans <<el;
	
}