首页 > 代码库 > bzoj1016[JSOI2008]最小生成树计数
bzoj1016[JSOI2008]最小生成树计数
Description
现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树,而希望知道这个图中有多少个不同的最小生成树。(如果两颗最小生成树中至少有一条边不同,则这两个最小生成树就是不同的)。由于不同的最小生成树可能很多,所以你只需要输出方案数对31011的模就可以了。
Input
第一行包含两个数,n和m,其中1<=n<=100; 1<=m<=1000; 表示该无向图的节点数和边数。每个节点用1~n的整数编号。接下来的m行,每行包含两个整数:a, b, c,表示节点a, b之间的边的权值为c,其中1<=c<=1,000,000,000。数据保证不会出现自回边和重边。注意:具有相同权值的边不会超过10条。
Output
输出不同的最小生成树有多少个。你只需要输出数量对31011的模就可以了。
Sample Input
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1
Sample Output
发现最小生成树的形态是固定的。
即如果有一颗最小生成树,则所有最小生成树所使用的相同权值的边的数量是一样的,并且每次构出的点都是一样的。
就是说每次都是相同的点被相同权值的边给连接起来。这个简单的证明就是如果有不同权值的边连上的相同的点,那么一定会有更优的生成树。
于是知道了这两个性质这题就很好搞了,排序之后先做一遍最小生成树,得出了每种权值所用的边的数量,然后打一个大暴力,枚举相同权值的边,然后并查集暴力判环,得出某种边权值的边的选择方案,然后乘法原理统计答案,组合数效率,因为相同权值的边最多有10条,所以最坏效率是20个C(10,5),发现效率是很OK的,如果不用并查集判环,复杂度就是满的,判环相当于大量剪枝,于是发现实际上暴力根本达不到满复杂度的效率,大量数据直接0.015s秒出。
P.S. 请注意判没有生成树的情况。
1 program award(input,output); 2 const 3 cs=31011; 4 var 5 father:array[0..110]of longint; 6 a,b,w,l,r,num:array[0..1010]of longint; 7 n,m,i,j,cnt,x,y,ans:longint; 8 procedure sort(q,h:longint); 9 var 10 i,j,x,t:longint; 11 begin 12 i:=q;j:=h;x:=w[(i+j)>>1]; 13 repeat 14 while w[i]<x do inc(i); 15 while x<w[j] do dec(j); 16 if i<=j then 17 begin 18 t:=a[i];a[i]:=a[j];a[j]:=t; 19 t:=b[i];b[i]:=b[j];b[j]:=t; 20 t:=w[i];w[i]:=w[j];w[j]:=t; 21 inc(i);dec(j); 22 end; 23 until i>j; 24 if j>q then sort(q,j); 25 if i<h then sort(i,h); 26 end; 27 function find(k:longint):longint; 28 begin 29 if father[k]=k then exit(k) else exit(find(father[k])); 30 end; 31 procedure dfs(k,s:longint); 32 var 33 x,y:longint; 34 begin 35 if k=r[i]+1 then begin if s=num[i] then inc(j);exit; end; 36 x:=find(a[k]);y:=find(b[k]); 37 if x<>y then 38 begin 39 father[x]:=y; 40 dfs(k+1,s+1); 41 father[x]:=x; 42 end; 43 dfs(k+1,s); 44 end; 45 begin 46 assign(input,‘award.in‘);assign(output,‘award.out‘);reset(input);rewrite(output); 47 readln(n,m); 48 for i:=1 to m do readln(a[i],b[i],w[i]); 49 sort(1,m); 50 for i:=1 to n do father[i]:=i; 51 w[0]:=0;j:=0;cnt:=0; 52 fillchar(num,sizeof(num),0); 53 for i:=1 to m do 54 begin 55 if w[i]<>w[i-1] then begin r[cnt]:=i-1;inc(cnt);l[cnt]:=i; end; 56 x:=find(a[i]);y:=find(b[i]); 57 if x<>y then begin father[x]:=y;inc(num[cnt]);inc(j); end; 58 end; 59 r[cnt]:=m; 60 if j<n-1 then begin write(0);close(input);close(output);halt; end; 61 ans:=1; 62 for i:=1 to n do father[i]:=i; 63 for i:=1 to cnt do 64 begin 65 j:=0; 66 dfs(l[i],0); 67 ans:=ans*j mod cs; 68 for j:=l[i] to r[i] do 69 begin 70 x:=find(a[j]);y:=find(b[j]); 71 if x<>y then father[x]:=y; 72 end; 73 end; 74 write(ans); 75 close(input);close(output); 76 end.
bzoj1016[JSOI2008]最小生成树计数