题目意思:有多个城市,多条路,路都是双向的,有一些城市有机器人大军,我们想通过破坏城市之间的城市来断绝机器人大军的联系,并且用最少的时间。
用krusual算法,并用mark标记存在有机器人的城市,有的两个城市之间的道路只有的1个机器人大军,剩下的就是要破坏的边。。。
#include"stdio.h" #include"stdlib.h" #include"string.h" int mark[100001],set[100001]; __int64 ans; struct node { int x,y,t; }aa[100001]; int find(int x) { if(x==set[x]) return x; return set[x]=find(set[x]); } int cmp(const void*a,const void*b) { return (*(struct node*)b).t-(*(struct node*)a).t; } void merge(int x,int y) { int fx,fy; fx=find(x); fy=find(y); if(fx==fy)return ; if(fx<fy) { set[fy]=fx; mark[fx]+=mark[fy]; } else { set[fx]=fy; mark[fy]+=mark[fx]; } } int main() { int T,n,m,i,a,b,c,k,x,y; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); memset(mark,0,sizeof(mark)); for(i=0;i<=n;i++) set[i]=i; ans=0; k=0; for(i=0;i<n-1;i++) { scanf("%d%d%d",&a,&b,&c); aa[k].x=a; aa[k].y=b; aa[k].t=c; k++; ans+=c; } qsort(aa,k,sizeof(aa[0]),cmp); for(i=0;i<m;i++) { scanf("%d",&a); mark[a]=1; } for(i=0;i<k;i++) { x=find(aa[i].x); y=find(aa[i].y); //两个城市之间最多有一个城市有机器人 if(mark[x]+mark[y]<=1) { merge(x,y); ans-=aa[i].t; } } printf("%I64d\n",ans); } return 0; }