前排资瓷
by Hokage @ 2019-06-15 16:13:34
将sort(a+1,a+n+1,cmp);改为sort(a+1,a+m+1,cmp);
by wangwenyu1 @ 2021-08-09 16:07:06
AC代码:
```
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100010;
int n,m,k,f[MAXN],sum;
struct ma{
int u,v,w;
}a[MAXN];
bool cmp(ma x,ma y){
return x.w>y.w;
}
int fi(int x){
if(f[x]!=x)f[x]=fi(f[x]);
return f[x];
}
void me(int x,int y){
f[x]=y;return;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++){
cin>>a[i].u>>a[i].v>>a[i].w;
}
for(int i=1;i<=n;i++)f[i]=i;
sort(a+1,a+m+1,cmp);
int p=0,q=0;
for(int i=1,j=0;i<=m;i++){
p=fi(a[i].u);
q=fi(a[i].v);
if(p!=q){
me(p,q);
sum+=a[i].w;
j++;
}
if(j==k)break;
}
printf("%d",sum);
return 0;
}
```
by wangwenyu1 @ 2021-08-09 16:09:58