自动搬运

查看原文

来自洛谷，原作者为

	星爵 **

搬运于2025-08-24 21:34:14，当前版本为作者最后更新于2017-08-30 14:24:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

模拟赛上做的题

就排个序

然后做 k 条边的最大生成树

然后就莫名奇妙的AC了

然后...

就没有然后了

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,k,f[100100],ans;
struct no
{
    int x,y,z;
}a[100100];
bool comp (const no & a,const no &b)
{
    return a.z>b.z;
}
int find(int x)
{
    if(f[x]!=x)
        f[x]=find(f[x]);
    return f[x];
}
void un(int x,int y)
{
    f[x]=y;
}
int main()
{
    freopen("carpet.in","r",stdin);
    freopen("carpet.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
    sort(a+1,a+m+1,comp);
    for(int i=1;i<=n;i++)//并查集，初始时每个祖先都是自己
        f[i]=i;
    for(int i=1,kk=0;i<=m&&kk<k;i++)
    {
        int l=find(a[i].x),r=find(a[i].y);
        if(l!=r)//不在同一集合就合并
        {
            un(l,r);
            kk++;//计数
            ans+=a[i].z;
        }
    }
    printf("%d",ans);
    return 0;
}