洛谷4208 [JSOI2008]最小生成树计数

Luogu

BZOJ

分析

似乎可以用矩阵树定理做,然而我不会。

性质:所有最小生成树中,每种权值的边的数量是相同的,每种权值的边的作用是相同的。

先跑一遍$\mathrm{Kruskal}$,得出每种边权的边所需的数量。

注意:具有相同权值的边不会超过10条。

所以可以对每种边权的边爆搜,得出方案数,再用乘法原理乘起来。

然后并查集不能路径压缩,不然dfs难以回溯。

要特判没有最小生成树的情况。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=100+10;
const int MAXM=1000+10;
const int MOD=31011;

struct Edge { int u,v,w; } e[MAXM];
inline int cmp(Edge a,Edge b) { return a.w<b.w; }
int n,m;

int root[MAXN];
inline void init(int n) { for (re int i=1;i<=n;++i) root[i]=i; }
inline int find(int x) { return x==root[x]?x:find(root[x]); }

int l[MAXM],r[MAXM],s[MAXM],cnt=0;
int sum=0;

inline void dfs(int id,int pos,int k) {
    if (k>s[id]) return; //小剪枝
    if (pos==r[id]+1) {
        if (k==s[id]) ++sum;
        return;
    }
    int p=find(e[pos].u),q=find(e[pos].v);
    if (p!=q) {
        root[p]=q;
        dfs(id,pos+1,k+1); //选
        root[p]=p,root[q]=q;
    }
    dfs(id,pos+1,k); //不选
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i)
        e[i].u=read(),e[i].v=read(),e[i].w=read();
    sort(e+1,e+m+1,cmp);
    init(n); int tot=0;
    for (re int i=1;i<=m;++i) {
        if (e[i].w!=e[i-1].w) l[++cnt]=i,r[cnt-1]=i-1;
        int p=find(e[i].u),q=find(e[i].v);
        if (p!=q)
            ++tot,++s[cnt],root[p]=q;
    }
    r[cnt]=m;
    if (tot!=n-1) { puts("0"); return 0; }
    init(n); int ans=1;
    for (re int i=1;i<=cnt;++i) {
        sum=0; dfs(i,l[i],0);
        ans=(ans*sum)%MOD;
        for (re int j=l[i];j<=r[i];++j) {
            int p=find(e[j].u),q=find(e[j].v);
            if (p!=q) root[p]=q;
        }
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 24 日 09 : 01 PM

发表评论