hdu 4313 Matrix 并查集 多校联合赛（二） 第四题

这道提问在这哥宫殿里最上的权值和是机器不向联

可以用并查集一做，思想又有点想克鲁斯卡尔，想将所有边从大到小排序，然后加边，让点都指向把机器，如果线的两个点都指向机器了，当然就吧这个边加到sum里，最后sum就是答案啦

#include<iostream>#include<cstdio>#include<algorithm>using namespace std;#define N 100005struct node{    int x;    int y;    int s;}a[N];bool cmp(node a,node b){    return a.x>b.s;}int vis[N],pa[N];int find(int x){    if(x!=pa[x])        pa[x]=find(pa[x]);    return pa[x];}int main(){//    freopen("in.txt","r",stdin);    int t,x,y,z,n,k,q;    scanf("%d",&t);    while(t--){        scanf("%d%d",&n,&k);        for(int i=0;i<n;i++){            vis[i]=0;            pa[i]=i;        }        for(int i=0;i<n-1;i++)            scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].s);        for(int i=0;i<k;i++){            scanf("%d",&q);            vis[q]=1;        }        sort(a,a+n-1,cmp);        long long sum=0;        for(int i=0;i<n-1;i++){            x=find(a[i].x);            y=find(a[i].y); //           cout<<vis[x]<<" "<<vis[y]<<endl;            if(vis[x]&&vis[y])                sum+=a[i].s;            else if(vis[x])                pa[y]=x;            else if(vis[y])                pa[x]=y;            else                pa[x]=y;        }        cout<<sum<<endl;    }}