「JSOI 2008」最小生成树计数

Description

题目链接:BZOJ 1016

给出一个由 $n$ 个点和 $m$ 条边构成的简单无向加权图。你不满足于求出这个图的最小生成树,而希望知道这个图中有多少个不同的最小生成树。(两棵最小生成树是不同的当且仅当它们有至少有一条边不同)。方案数对 $31011$ 取模。

数据范围:$1\le n\le 100$,$1\le m\le 1000$


Solution

简化版

由于在 $\text{MST}$ 中,每种权值的边的数量是固定的,那么我们先统计出每种权值需要多少条边,记为 $c_i$。

我们发现具有相同权值的边的数量不超过 $10$ 条,那么我们暴力枚举第 $i$ 种权值的边选择哪 $c_i$ 条,然后根据乘法原理来统计答案。(这个算法已经可以通过本题)

注意:我们为了能够快速分开连通块,并查集中不能使用路径压缩

时间复杂度:$O(2^{10}m)​$

加强版

我们考虑加强版:每种权值的边不超过 $100$ 条。我们就需要矩阵树定理了。

注意到 $\text{MST}$ 有如下性质:

  1. 每种权值的边的数量是固定的。
  2. 不同的生成树中,某一种权值的边任意加入需要的数量后,形成的联通块状态是一样的

这样一来,我们可以枚举树边的权值 $i$,把权值不是 $i$ 的树边都加入图中后进行缩点;对于权值为 $i$ 的原图中的边,在缩点后的图中构造基尔霍夫矩阵,用矩阵树定理求出方案数。

最终的答案也是根据乘法原理计算。

时间复杂度:$O(n^3\log n)$(大概是这样吧,这个算法我不怎么会算呀 QAQ)


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
#include <cstdio>
#include <algorithm>

const int N=105,M=1e3+5;
const int mod=31011;
int n,m,cnt,sum,l[M],r[M],c[M],fa[N];
struct Edge {
int u,v,w;
bool operator < (const Edge &b) const {
return w<b.w;
}
}e[M];

int find(int x) {
return fa[x]==x?x:find(fa[x]);
}
void dfs(int now,int x,int num) {
if(now>r[x]) {
sum+=(num==c[x]);
return;
}
int fu=find(e[now].u),fv=find(e[now].v);
if(fu!=fv) {
fa[fu]=fv;
dfs(now+1,x,num+1);
fa[fu]=fu,fa[fv]=fv;
}
dfs(now+1,x,num);
}
int main() {
scanf("%d%d",&n,&m);
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);
for(int i=1;i<=n;++i) fa[i]=i;
int tot=0;
for(int i=1;i<=m;++i) {
if(e[i].w!=e[i-1].w) r[cnt]=i-1,l[++cnt]=i;
int fu=find(e[i].u),fv=find(e[i].v);
if(fu!=fv) ++c[cnt],fa[fu]=fv,++tot;
}
r[cnt]=m;
if(tot!=n-1) return puts("0"),0;
for(int i=1;i<=n;++i) fa[i]=i;
int ans=1;
for(int i=1;i<=cnt;++i) {
sum=0,dfs(l[i],i,0),ans=ans*sum%mod;
for(int j=l[i];j<=r[i];++j) fa[find(e[j].u)]=find(e[j].v);
}
printf("%d\n",ans);
return 0;
}

加强版

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N=105,M=1e3+5;
const int mod=31011;
int n,m,tot,fa[N],a[N][N],bel[N],val[N];
struct Edge {
int u,v,w;
bool operator < (const Edge &b) const {
return w<b.w;
}
}e[M],tr[N];

int find(int x) {
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void init() {
for(int i=1;i<=n;++i) fa[i]=i;
}
void add(int u,int v) {
--a[u][v],--a[v][u],++a[u][u],++a[v][v];
}
void merge(int x,int y) {
fa[find(x)]=find(y);
}
int Gauss(int n) {
int ans=1;
for(int i=1;i<=n;++i) {
for(int k=i+1;k<=n;++k) {
while(a[k][i]) {
int d=a[i][i]/a[k][i];
for(int j=i;j<=n;++j) a[i][j]=(a[i][j]-1LL*d*a[k][j]%mod+mod)%mod;
std::swap(a[i],a[k]),ans=-ans;
}
}
ans=1LL*ans*a[i][i]%mod,ans=(ans+mod)%mod;
}
return ans;
}
bool kruskal() {
std::sort(e+1,e+m+1);
init();
int cnt=0;
for(int i=1;i<=m;++i) {
int fu=find(e[i].u),fv=find(e[i].v);
if(fu==fv) continue;
fa[fu]=fv,tr[++cnt]=e[i];
if(e[i].w!=val[tot]) val[++tot]=e[i].w;
}
return cnt==n-1;
}
void addTreeEdge(int v) {
for(int i=1;i<n&&tr[i].w!=v;++i) merge(tr[i].u,tr[i].v);
for(int i=n-1;i&&tr[i].w!=v;--i) merge(tr[i].u,tr[i].v);
}
int getblock() {
int blo=0;
for(int i=1;i<=n;++i) if(find(i)==i) bel[i]=++blo;
for(int i=1;i<=n;++i) bel[i]=bel[find(i)];
return blo;
}
void rebuild(int v) {
memset(a,0,sizeof(a));
for(int i=1;i<=m;++i) if(e[i].w==v) add(bel[e[i].u],bel[e[i].v]);
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
if(!kruskal()) return puts("0"),0;
int ans=1;
for(int i=1;i<=tot;++i) {
init();
addTreeEdge(val[i]);
int blo=getblock();
rebuild(val[i]);
ans=1LL*ans*Gauss(blo-1)%mod;
}
printf("%d\n",ans);
return 0;
}
0%