AcWing 1141. 局域网
原题链接
简单
作者:
Dear_You
,
2019-11-26 08:15:33
,
所有人可见
,
阅读 1285
C++ 代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define RG register
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int N=1e3+10;
int n,k,ans,num,tot;
int pre[N];
struct nkl
{
int x,y,z;
}e[N];
inline int god(nkl aa,nkl bb)
{
return aa.z<bb.z;
}
inline int find(int x)
{
if(x==pre[x]) return x;
return pre[x]=find(pre[x]);
}
int main()
{
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++) pre[i]=i;
for (int i=1;i<=k;i++)
{
scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
ans+=e[i].z;
}
sort(e+1,e+k+1,god);
for (int i=1;i<=k;i++)
{
int k=find(e[i].x),l=find(e[i].y);
if(k==l) continue;
pre[k]=l;
num++;
tot+=e[i].z;
if(num==n-1) break;
}
printf("%d\n",ans-tot);
return 0;
}
tql
大佬又来了QwQ