BZOJ1016 [JSOI2008]最小生成树计数

浏览数：42 / 时间：2015年06月09日

江苏就是江苏啊，题目质量高。

看到题的时候只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 begin
106     fa[f1] := f2;
107     sub(l + 1, r, num - 1);
108     fa[f1] := f1;
109   end;
110 end;
111  
112 procedure make_ans;
113 var
114   i, j, f1, f2 : longint;
115  
116 begin
117   for i := 1 to n do
118     fa[i] := i;
119   ans := 1;
120   for i := 1 to k do begin
121     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 begin
125       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 begin
133   readln(n, m);
134   for i := 1 to m do begin
135     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 do
142     if c[i] <> c[i - 1] then begin
143       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 do
151     if fa[i] = i then
152       if flag then flag := false
153       else begin
154         writeln(0);
155         exit;
156       end;
157   writeln(ans);
158 end.