爆零求助
  • 板块P2820 局域网
  • 楼主czk111
  • 当前回复8
  • 已保存回复8
  • 发布时间2023/8/17 20:02
  • 上次更新2023/11/24 20:32:46
查看原帖
爆零求助
682044
czk111楼主2023/8/17 20:02
#include <bits/stdc++.h>
using namespace std;
int f[10010];
struct node{
	int from,to,data;
}a[10010];
int n,m,ans,t,sum;
bool cmp(node a,node b){
	return a.data<b.data; 
}
int find(int x){
	if(f[x]==x) return x;
	else return f[x]=find(f[x]);
}
void k(){
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
		if(find(a[i].from)==find(a[i].to))continue;
		sum+=a[i].data;
		f[find(a[i].from)]=find(a[i].to);
		t++;
		if(t==n)return;
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<=m;i++){
		cin>>a[i].from>>a[i].to>>a[i].data;
		ans+=a[i].data;
	}
	k();
	cout<<ans-sum;
}
2023/8/17 20:02
加载中...