并查集
初始时没有边加入,将所有边按权值从大到小排序,然后依次判断每一个边两端的顶点是否是均为machine节点,
如果是则应删除这条边,否则加入这条边,然后在并查集合并时尽量让根节点为machine节点。
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<algorithm> using namespace std; #define N 100100 struct edge { int s,d; int cost; }e[N]; int num=0,n,f[N]; bool vis[N]; int find(int a) { if(a!=f[a]) f[a]=find(f[a]); return f[a]; } bool cmp(struct edge a,struct edge b) { return a.cost>b.cost; } void addedge(int a,int b,int c) { e[num].s=a;e[num].d=b; e[num++].cost=c; } int main() { int i,j,k,t,a,b,c; __int64 sum; scanf("%d",&t); while(t--) { num=0; scanf("%d%d",&n,&k); memset(vis,false,sizeof(vis)); for(i=0;i<n;i++) f[i]=i; for(i=1;i<n;i++) { scanf("%d%d%d",&a,&b,&c); addedge(a,b,c); } for(i=0;i<k;i++) { scanf("%d",&a); vis[a]=true; } sort(e,e+num,cmp); sum=0; for(i=0;i<num;i++) { a=find(e[i].s);b=find(e[i].d); if(a!=b&&vis[a]==true&&vis[b]==true) { sum+=e[i].cost; } else { if(vis[a]) f[b]=a; else f[a]=b; } } printf("%I64d\n",sum); } return 0; }