AcWing 1141. 局域网
原题链接
简单
作者:
ZTEG
,
2019-11-24 14:42:57
,
所有人可见
,
阅读 1270
#include<bits/stdc++.h>
using namespace std;
int n,k;
struct oppo{
int from,to,s;
}rood[400];
bool rule(oppo a,oppo b)
{
return a.s<b.s;
}
int fa[205];//并查集
int ans;
int find(int x)//并查集
{
return fa[x]==x?x:fa[x]=find(fa[x]);//返回和路径压缩
}
int main()
{
cin>>n>>k;
for(int i=1;i<=k;i++)
{
scanf("%d %d %d",&rood[i].from,&rood[i].to,&rood[i].s);
if(!rood[i].s)
{
i--;
k--;
}
ans+=rood[i].s;
}
sort(rood+1,rood+k+1,rule);
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=k;i++)
{
int a=find(rood[i].from);
int b=find(rood[i].to);
if(a!=b)
{
fa[a]=b;
ans-=rood[i].s;
}
}
cout<<ans<<endl;
return 0;
}