社区讨论

14分求条!!!玄关

P3366【模板】最小生成树参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mhj2p0rw
此快照首次捕获于
2025/11/03 19:44
4 个月前
此快照最后确认于
2025/11/03 19:44
4 个月前
查看原帖

来个dalao帮一下吧

蒟蒻要不行了
CPP
//https://www.luogu.com.cn/record/239577483
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')f*=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x*f;
}
struct node{
	int to,we; 
};
int fa[N];
struct P{
	int U,V,W;
	bool operator < (const P other)const{
		return W>other.W;
	}
};
priority_queue<P> q;
vector<node> mp[N];
int n,m;
int f(int x){
	if(fa[x]!=x)fa[x]=f(fa[x]);
	return fa[x];
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),w=read();
		mp[u].push_back({v,w});
		mp[v].push_back({u,w});
		q.push({u,v,w});
	}
	int ans=0;
	while(!q.empty()){
		P cu=q.top();
		q.pop();
		if(f(cu.U)==f(cu.V)){
			continue;
		}
		ans+=cu.W;
		fa[cu.U]=fa[cu.V]; 
	}
	cout<<ans;
	return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...