这不是模板吗?
查看原帖
这不是模板吗?
796667
ZY_jiang楼主2024/3/13 16:05
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lulu pair<ll,int>
#define ls u/2
#define rs (u/2)+1
#define F(i,j,n) for(int i=(j);i<=(n);i++)
const int N=2e5+10;
vector <ll> adj[N];
priority_queue< lulu , vector<lulu> , greater<lulu> > maxpairq;
priority_queue< ll , vector<ll> , greater<ll> > maxq;
priority_queue< lulu ,vector <lulu> > minpairq;
priority_queue< ll ,vector <ll> > minq;
ll fa[N];
queue <ll> q;
deque <ll> pq;
struct node{
	ll u,v,w;
}tr[N];
ll sum1,sum2,sum3,n,m,a[N],sum[N],ans;
int vis[N];
ll dp[110][110],f[N];
string s1,s2,s3,s;
char ch[N],chara;
void init(){
	F(i,1,N){
		fa[i]=i;
	}
}
ll find(ll x){
	if(fa[x]==x){
		return x;
	}
	else return fa[x]=find(fa[x]);
}
bool cmp(node a,node b){
	return a.w<b.w;
}
ll kruskal(){
	ll sum=0,cnt=0;
	sort(tr+1,tr+m+1,cmp);
	F(i,1,m){
		ll u=find(tr[i].u);
		ll v=find(tr[i].v);
		ll w=tr[i].w;
		if(u==v) continue;
		fa[u]=v;
		sum+=w;
		cnt++;
	}
	return sum;
}
int main(){
	init();
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>tr[i].u>>tr[i].v>>tr[i].w;
	}
	ans=kruskal();
	cout<<ans;
	return 0;
}
2024/3/13 16:05
加载中...