题解 P4208 【[JSOI2008]最小生成树计数】
Siyuan
2019-02-08 11:15:13
[$$\Large\texttt{My Blog}$$](https://hydingsy.github.io/articles/problem-JSOI-2008-MST-Count/)
---
## Description
> 题目链接：[Luogu 4208](https://www.luogu.org/problemnew/show/P4208)
给出一个由 $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
### 简化版
```cpp
#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;
}
```
### 加强版
```cpp
#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;
}
```