1729. blockenemy (Standard IO)Time Limits: 1000 ms Memory Limits: 128000 KB Detailed Limits
Description你在玩电子游戏的时候遇到了麻烦。。。。。。 你玩的游戏是在一个虚拟的城市里进行，这个城市里有n个点，都从0~n-1编了号，每两个点之间有且仅有一条路径。现在，你的敌人到这个城市来踩点了!!!为了阻止他们更好的踩点， 你决定切断他们所有踩点人员的联系，使他们孤军作战，然后在各个击破。但是这就要切断某些街道，而你每切断一条路，市民就会产生相对的不满值，不满值越大，城市的和谐度就越小。所以你现在需要知道为了使踩点人员所在的点两两之间不联通所切断的边产生的最小不满值是多少？Input
第一行一个数：n n<=50 以下n-1行，每行3个数 a，b，c 表示a点和b点之间有条路，切断这条路的不满值为c 以下若干行 每行一个数，表示踩点人员的位置
Output
一个数，最小不满值
Sample Input
5 1 0 1 1 2 2 0 3 3 4 0 4 3 2 4
Sample Output
4
分析：
这道题用并查集来实现。将所有边由大到小依次加入图中，加入后若无敌人连通，则保留；若有敌人连通，则删除，并统计答案。
代码：
const maxn=50; var a:array [0..maxn,1..3] of longint; father,expert:array [0..maxn] of longint; n,x,y,ans:longint; procedure qsort(l,r:longint); var i,j,mid:longint; begin i:=l;j:=r;mid:=a[(l+r)div 2,3]; repeat while a[i,3]>mid do inc(i); while a[j,3]<mid do dec(j); if i<=j then begin a[0]:=a[i]; a[i]:=a[j]; a[j]:=a[0]; inc(i);dec(j); end; until i>j; if l<j then qsort(l,j); if i<r then qsort(i,r); end; procedure init; var i:longint; begin readln(n); for i:=1 to n-1 do begin readln(a[i,1],a[i,2],a[i,3]); ans:=ans+a[i,3]; inc(a[i,1]);inc(a[i,2]); end; qsort(1,n-1); while not eof do begin readln(i); expert[i+1]:=1; end; end; function getfather(x:longint):longint; var i:longint; begin if father[x]=x then exit(x); i:=getfather(father[x]); father[x]:=i; exit(i); end; procedure connect(x,y:longint); var i,j:longint; begin i:=getfather(x); j:=getfather(y); father[i]:=j; expert[j]:=expert[j]+expert[i]; end; procedure main; var i:longint; begin for i:=1 to n do father[i]:=i; for i:=1 to n-1 do begin x:=getfather(a[i,1]); y:=getfather(a[i,2]); if x<>y then if expert[x]+expert[y]<2 then begin connect(a[i,1],a[i,2]); ans:=ans-a[i,3]; end; end; writeln(ans); end; begin assign(input,'blockenemy.in');reset(input); assign(output,'blockenemy.out');rewrite(output); init; main; close(input);close(output); end.
