[BZOJ1016] [JSOI2008] 最小生成树计数

qwq

现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树,而希望知道这个图中有多少个不同的最小生成树。(如果两颗最小生成树中至少有一条边不同,则这两个最小生成树就是不同的)。由于不同的最小生成树可能很多,所以你只需要输出方案数对31011的模就可以了。

思路

引理 最小生成树中边权大小相等的边个数总是相同

首先在n个独立点中连上所有边权为w的边能将图分成k个联通块。

现在我们考虑像最小生成树一样的加边,即无联通才加边,最后形成的联通森林一定是有k个树,边数一定是n - k。

先求一边kruskal,之后所有的方案的每组边权相同的边个数相同。

所以我们考虑每一组边权相同的边,枚举加哪些边能满足方案。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <cstdio>
#include <algorithm>
#include <cctype>
#include <cstring>
const int N = 110,M = 1010,MOD = 31011;
int n,m;
struct edge{int u,v,w;}E[M];
struct seg{int l,r,v;}S[M];int scnt = 0;
inline bool cmp (const edge &a,const edge &b){return a.w < b.w;}
int fa[N];
inline int find(int u){return u == fa[u] ? u : find(fa[u]);}
int sum = 0;
inline void dfs(int u,int id,int k)
{
if(id == S[u].r + 1)
{
if(k == S[u].v) sum++;
return;
}
int p = find(E[id].u),q = find(E[id].v);
if(p != q)
{
fa[p] = q;
dfs(u,id + 1,k + 1);
fa[p] = p;fa[q] = q;
}
dfs(u,id + 1,k);
}
int main()
{
memset(E,0,sizeof(E));memset(S,0,sizeof(S));
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++) fa[i] = i;
for(int i = 1;i <= m;i++) scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].w);
std::sort(E + 1,E + m + 1,cmp);
int tot = 0;
for(int i = 1;i <= m;i++)
{
int p = find(E[i].u),q = find(E[i].v);
if(E[i].w != E[i - 1].w){S[++scnt].l = i;S[scnt - 1].r = i - 1;}
if(p != q){fa[p] = q;S[scnt].v++;tot++;}
}
S[scnt].r = m;
if(tot != n - 1) {puts("0");return 0;}
for(int i = 1;i <= n;i++) fa[i] = i;
int ans = 1;
for(int i = 1;i <= scnt;i++)
{
sum = 0;
dfs(i,S[i].l,0);
ans = 1LL * ans * sum % MOD;
for(int j = S[i].l;j <= S[i].r;j++)
{
int p = find(E[j].u),q = find(E[j].v);
if(p != q) fa[p] = q;
}
}
printf("%d\n",ans);
return 0;
}