【题目】:The Unique MST
【来源】:POJ1679
【关键字】:图论 次小生成树
//================================================================================================
【分析】:先构造最小生成树,再在MST中删边,找次小生成树.
【小结】:刘老师的论文
//================================================================================================
【代码】:
View Code 1 type 2 rec = record 3 x, y, d: longint; 4 end; 5 var 6 t, i, n, m, ans, j: longint; 7 a: array[0..10010] of boolean; 8 e: array[0..10010] of rec; 9 f: array[0..4000] of longint; 10 function get(k: longint):longint; 11 begin 12 if f[k] = k then exit(k); 13 f[k] := get(f[k]); 14 get := f[k]; 15 end; 16 procedure qs(l, r: longint); 17 var 18 i, j, mid: longint; 19 t: rec; 20 begin 21 i := l; 22 j := r; 23 mid := e[(l+r) shr 1].d; 24 repeat 25 while e[i].d < mid do inc(i); 26 while e[j].d > mid do dec(j); 27 if i <= j then 28 begin 29 t := e[i]; 30 e[i] := e[j]; 31 e[j] := t; 32 inc(i); 33 dec(j); 34 end; 35 until i > j; 36 if l < j then qs(l,j); 37 if i < r then qs(i,r); 38 end; 39 function judge:boolean; 40 var 41 p, i, j, x, y, now: longint; 42 begin 43 for j := 1 to m do 44 if not a[j] then 45 begin 46 p := 0; 47 now := 0; 48 for i := 1 to n do f[i] := i; 49 i := 1; 50 while (i <= m) and (p < n-1) do 51 begin 52 x := get(e[i].x); 53 y := get(e[i].y); 54 if (x <> y) and (i <> j) then 55 begin 56 f[x] := y; 57 inc(now,e[i].d); 58 inc(p); 59 end; 60 inc(i); 61 end; 62 if p <> n-1 then now := -1; 63 if now = ans then exit(true); 64 end; 65 exit(false); 66 end; 67 procedure kur; 68 var 69 p, i, x, y: longint; 70 begin 71 p := 0; 72 ans := 0; 73 for i := 1 to n do f[i] := i; 74 for i := 1 to m do a[i] := true; 75 i := 1; 76 while (i <= m) or (p < n-1) do 77 begin 78 x := get(e[i].x); 79 y := get(e[i].y); 80 if x <> y then 81 begin 82 f[x] := y; 83 inc(ans,e[i].d); 84 inc(p); 85 a[i] := false; 86 end; 87 inc(i); 88 end; 89 if p <> n-1 then ans := -1; 90 end; 91 begin 92 readln(t); 93 for j := 1 to t do 94 begin 95 readln(n,m); 96 for i := 1 to m do 97 readln(e[i].x,e[i].y,e[i].d); 98 qs(1,m); 99 kur; 100 if judge then writeln('Not Unique!') else writeln(ans); 101 end; 102 end.