「JSOI 2008」最小生成树计数

发表于 | | 阅读次数:
字数统计: 1.2k 字

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%