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

题意

给一个无向简单图，求最小生成树的个数，对 $31011$ 取模。

其中点数 $n\le 100$ ，边数 $m\le 1000$ 。

题解

有个性质：在不同的最小生成树中，每种权值的边的数量一定相同。

这道题又有个限制：具有相同权值的边不会超过 $10$ 条，那么就可以直接用那个性质来暴力了。

先跑出来最小生成树，记录下来每种权值的边的数量 $t\_cnt[]$ 以及每种权值的起始位置 $l[]$ 和终止位置 $r[]$ 。然后dfs枚举每种权值的边如何选取，用并查集判环，最后乘法原理统计答案即可。

#include<bits/stdc++.h>
#define ha 31011

using namespace std;

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

struct Edge {
    int st,ed,w;
} edge[1005];
int n,m,fa[105],l[1005],r[1005],t_cnt[1005];

inline bool cmp(Edge x,Edge y) { return x.w<y.w; }

inline void init() { for (int i=1;i<=n;i++) fa[i]=i; }

int getfa(int x) { return (x==fa[x]) ? x : getfa(fa[x]); }

inline bool merge(int x,int y)
{
    int gfx=getfa(x),gfy=getfa(y);
    if (gfx==gfy) return 0;
    fa[gfx]=gfy;
    return 1;
}

int dfs(int typ,int now,int cnt)
{
    if (now>r[typ]) return cnt==t_cnt[typ];
    int ans=0;
    int x=getfa(edge[now].st),y=getfa(edge[now].ed);
    if (x!=y)
    {
        fa[x]=y;
        ans+=dfs(typ,now+1,cnt+1);
        fa[x]=x; fa[y]=y;
    }
    ans+=dfs(typ,now+1,cnt);
    return ans;
}

int main()
{
    n=read(); m=read();
    for (int i=1;i<=m;i++) edge[i].st=read(),edge[i].ed=read(),edge[i].w=read();
    sort(edge+1,edge+m+1,cmp);
    init();
    int typ=0,cnt=0;
    for (int i=1;i<=m;i++)
    {
        if (edge[i].w!=edge[i-1].w) r[typ]=i-1,l[++typ]=i;
        int x=edge[i].st,y=edge[i].ed;
        if (!merge(x,y)) continue;
        cnt++;
        t_cnt[typ]++;
    }
    if (cnt!=n-1)
    {
        printf("0");
        return 0;
    }
    r[typ]=m;
    init();
    int ans=1;
    for (int i=1;i<=typ;i++)
    {
        ans=(ans*dfs(i,l[i],0))%ha;
        for (int j=l[i];j<=r[i];j++) merge(edge[j].st,edge[j].ed);
    }
    printf("%d",ans);
    return 0;
}