hdu4313 Matrix（kruskal思想+并查集）

题意：

给定一棵n个节点的树，树边有边权
现在有k个坏点，要求删除树中若干条边，满足k个坏点两两不连通，问删除的最小边权和是多少

数据范围：n<=1e5

解法：

反过来想，将问题转化为计算能保留的最大边权和

根据kruskal算法思想贪心地对边按边权从大到小排序，然后遍历，
如果当前边不会令两个坏点相连那么可以保留，否则必须删
累加必须删的边的边权就能得到答案。
判断连接之后是否会使两个坏点相连可以用带权并查集维护连通块内坏点数量

code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxm=2e5+5;
struct Node{
    int a,b,c;
}e[maxm];
int pre[maxm];
int cnt[maxm];
int mark[maxm];
bool cmp(Node a,Node b){
    return a.c>b.c;
}
int ffind(int x){
    return pre[x]==x?x:pre[x]=ffind(pre[x]);
}
signed main(){
    ios::sync_with_stdio(0);
    int T;cin>>T;
    while(T--){
        //input
        int n,k;cin>>n>>k;
        for(int i=1;i<n;i++){
            cin>>e[i].a>>e[i].b>>e[i].c;
        }
        for(int i=0;i<n;i++)mark[i]=0;
        for(int i=1;i<=k;i++){
            int x;cin>>x;
            mark[x]=1;
        }
        for(int i=0;i<n;i++){
            pre[i]=i;cnt[i]=mark[i];
        }
        //
        sort(e+1,e+1+n-1,cmp);
        int ans=0;
        for(int i=1;i<n;i++){
            int x=ffind(e[i].a);
            int y=ffind(e[i].b);
            if(x!=y){
                if(cnt[x]&&cnt[y]){
                    ans+=e[i].c;
                }else{
                    pre[x]=y;
                    cnt[y]+=cnt[x];
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

---

本文地址：https://blog.csdn.net/weixin_44178736/article/details/107162611