首页 > 代码库 > BZOJ1016 [JSOI2008]最小生成树计数
BZOJ1016 [JSOI2008]最小生成树计数
江苏就是江苏啊，题目质量高。
看到题的时候只YY出了第一个性质：MST中边权相同的的边的个数是一定的。（证略，可以用反证法）
后来上网找题解，发现还有第二个性质：MST如果用Kruskal来做，做完长度为x的所有边以后，此时图的连通性是确定的。（这也是很明显的）
于是嘛。。。先算出每个长度的边的cnt，然后每次暴力枚举哪些边在MST中。
判断方式就是看新加的边有没有使得原来不联通的块联通，然后就做完了。
但是要注意的是，暴力枚举的时候并查集不能路径压缩，因为还要还原。
1 {$inline on} 2 3 const prime = 31011; 4 5 var 6 n, m, k, t : longint; 7 i, x, y, z : longint; 8 count, ans : longint; 9 a, b, c, p, cnt, fa : array[0..5000] of longint; 10 flag : boolean; 11 12 procedure add_edge(x, y, z : longint); inline; 13 begin 14 inc(t); 15 a[t] := x; 16 b[t] := y; 17 c[t] := z; 18 end; 19 20 procedure swap(x, y : longint); inline; 21 var 22 t : longint; 23 24 begin 25 t := a[x]; a[x] := a[y]; a[y] := t; 26 t := b[x]; b[x] := b[y]; b[y] := t; 27 t := c[x]; c[x] := c[y]; c[y] := t; 28 end; 29 30 procedure qsort(l, r : longint); 31 var 32 i, j, x : longint; 33 34 begin 35 i := l; 36 j := r; 37 x := c[(i + j) shr 1]; 38 repeat 39 while c[i] < x do inc(i); 40 while c[j] > x do dec(j); 41 if i <= j then begin 42 swap(i, j); 43 inc(i); 44 dec(j); 45 end; 46 until i > j; 47 if i < r then qsort(i, r); 48 if l < j then qsort(l, j); 49 end; 50 51 function find_fa(x : longint) : longint; 52 var 53 f : longint; 54 55 begin 56 f := fa[x]; 57 if f = x then exit(f); 58 f := find_fa(f); 59 fa[x] := f; 60 exit(f); 61 end; 62 63 procedure make_mst; 64 var 65 i, j, f1, f2 : longint; 66 67 begin 68 for i := 1 to n do 69 fa[i] := i; 70 j := 0; 71 fillchar(cnt, sizeof(cnt), 0); 72 for i := 1 to t do begin 73 if c[i] <> c[i - 1] then inc(j); 74 f1 := find_fa(a[i]); 75 f2 := find_fa(b[i]); 76 if f1 <> f2 then begin 77 inc(cnt[j]); 78 fa[f1] := f2; 79 end; 80 end; 81 end; 82 83 function find_f(x : longint) : longint; inline; 84 begin 85 while fa[x] <> x do 86 x := fa[x]; 87 exit(x); 88 end; 89 90 procedure sub(l, r, num : longint); 91 var 92 f1, f2 : longint; 93 94 begin 95 if num = 0 then begin 96 inc(count); 97 if count > prime then 98 count := count - prime; 99 exit;100 end;101 if l > r then exit;102 if r - l + 1 > num then sub(l + 1, r, num);103 f1 := find_f(a[l]);104 f2 := find_f(b[l]);105 if f1 <> f2 then begin106 fa[f1] := f2;107 sub(l + 1, r, num - 1);108 fa[f1] := f1;109 end;110 end;111 112 procedure make_ans;113 var114 i, j, f1, f2 : longint;115 116 begin117 for i := 1 to n do118 fa[i] := i;119 ans := 1;120 for i := 1 to k do begin121 count := 0;122 sub(p[i], p[i + 1] - 1, cnt[i]);123 ans := (ans * count) mod prime;124 for j := p[i] to p[i + 1] - 1 do begin125 f1 := find_fa(a[j]);126 f2 := find_fa(b[j]);127 if f1 <> f2 then fa[f1] := f2;128 end;129 end;130 end;131 132 begin133 readln(n, m);134 for i := 1 to m do begin135 read(x, y, z);136 add_edge(x, y, z);137 end;138 qsort(1, t);139 p[1] := 1;140 k := 1;141 for i := 2 to t do142 if c[i] <> c[i - 1] then begin143 inc(k);144 p[k] := i;145 end;146 p[k + 1] := t + 1;147 make_mst;148 make_ans;149 flag := true;150 for i := 1 to n do151 if fa[i] = i then152 if flag then flag := false153 else begin154 writeln(0);155 exit;156 end;157 writeln(ans);158 end.
BZOJ1016 [JSOI2008]最小生成树计数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。