P2121 题解

DuskDawn · 2023-08-14 14:11:21 · 个人记录

传送门

类似于求图的“最大生成树”，使用 Kruskal 求解即可。不同的是至多只能保留 k 条边。但这不影响我们求解，即使只选出了 k 条边，这 k 条边也不会构成环，且按照 Kruskal 的贪心策略这 k 条边一定是最优解。

#include <bits/stdc++.h>
using namespace std;
struct Edge{
    int u,v,w;
    bool operator<(const Edge &b)const{
        return w>b.w;
    }
}p[100001];
int n,m,k,ans,cnt;
int fa[100001];
int Find(int u){
    return u==fa[u]?u:fa[u]=Find(fa[u]);
}
int kruskal(){
    sort(p+1,p+m+1);
    for (int i=1;i<=m&&cnt<k;i++){//只选k条边即可
        int fu=Find(p[i].u),fv=Find(p[i].v);
        if (fu!=fv){
            fa[fv]=fu;
            ans+=p[i].w;
            cnt++;
        }
    }
    return ans;
}
int main(){
    cin>>n>>m>>k;
    for (int i=1;i<=n;i++){
        fa[i]=i;
    }
    for (int i=1;i<=m;i++){
        cin>>p[i].u>>p[i].v>>p[i].w;
    }
    cout<<kruskal();
    return 0;
}