JSOI2008 最小生成树计数

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

题解：

最小生成树的两个性质：

1、边权相等的边的个数一定。

2、做完边权为w的所有边时，图的连通性相同。

证明：

1、边权相等的边的个数不一样的话就不会都同时是最小生成树了。

2、假设每种方法的做完边权为w的连通性不同，那么假设i边和j边没有同时被选，那么我们完全可以在一种方案中加入i边（或j边），使得连通性增强，而后面费用更大的边用的更少，这样与这是最小生成树矛盾。于是，命题得证。

代码：不知为何，下面程序有bug，什么时候再回来A掉……

 1 type node1=record
 2      x,y,w:longint;
 3      end;
 4      node2=record
 5      l,r,v:longint;
 6      end;
 7 var e:array[0..2000] of node1;
 8     a:array[0..2000] of node2;
 9     i,n,m,ans,sum,xx,yy,cnt,tot,j:longint;
10     fa:array[0..2000] of longint;
11 function find(x:longint):longint;
12  begin
13  if fa[x]<>x then fa[x]:=find(fa[x]);
14  exit(fa[x]);
15  end;
16 procedure qsort(h,l:longint);
17  var i,j,m:longint;
18      tmp:node1;
19  begin
20  i:=h;j:=l;m:=e[(i+j)>>1].w;
21  repeat
22   while e[i].w<m do inc(i);
23   while e[j].w>m do dec(j);
24   if i<=j then
25    begin
26    tmp:=e[i];e[i]:=e[j];e[j]:=tmp;
27    inc(i);dec(j);
28    end;
29  until i>j;
30  if i<l then qsort(i,l);
31  if j>h then qsort(h,j);
32  end;
33 procedure init;
34  begin
35  readln(n,m);
36  for i:=1 to m do with e[i] do readln(x,y,w);
37  qsort(1,m);
38  cnt:=0;tot:=0;
39  for i:=1 to n do fa[i]:=i;
40  for i:=1 to m do
41   begin
42   if e[i].w<>e[i-1].w then
43    begin
44    a[cnt].r:=i-1;
45    inc(cnt);
46    a[cnt].l:=i;
47    end;
48   xx:=find(e[i].x);yy:=find(e[i].y);
49   if xx<>yy then
50    begin
51    fa[xx]:=yy;
52    inc(a[cnt].v);
53    inc(tot);
54    end;
55   end;
56  a[cnt].r:=m;
57  if tot<n-1 then begin writeln(0);halt;end;
58  end;
59 procedure dfs(x,now,k:longint);
60  var xx,yy:longint;
61  begin
62  if now=a[x].r+1 then
63   begin
64   if k=a[x].v then inc(sum);
65   exit;
66   end;
67  xx:=find(e[now].x);yy:=find(e[now].y);
68  if xx<>yy then
69   begin
70   fa[xx]:=yy;
71   dfs(x,now+1,k+1);
72   fa[xx]:=xx;fa[yy]:=yy;
73   end;
74  dfs(x,now+1,k);
75  end;
76 procedure main;
77  begin
78  for i:=1 to n do fa[i]:=i;
79  ans:=1;
80  for i:=1 to cnt do
81   begin
82   sum:=0;
83   dfs(i,a[i].l,0);
84   ans:=(ans*sum) mod 31011;
85   for j:=a[i].l to a[i].r do
86    begin
87    xx:=find(e[j].x);yy:=find(e[j].y);
88    if xx<>yy then fa[xx]:=yy;
89    end;
90   end;
91  writeln(ans);
92  end;
93 begin
94  init;
95  main;
96 end.