[JSOI2008]最小生成树计数 解题报告

解题报告 最小生成树

[JSOI2008]最小生成树计数

题面

有一张节点数为 $n$, 边数为 $m$ 的带权无向图 $(1\le n \le 100,\ 1 \le m \le 1000)$,
求这张图有多少棵不同的最小生成树,
其中相同权值的边不超过 $10$ 条.

思路

有一个定理/(结论?), 同一张图的不同最小生成树中, 每一种权值的边的数量相等, (并且从小到大把每种权值的边连完后, 图的连通性也一样).

所以权值不同的边之间没有干扰,
那我们只要分别计算每一种权值的边有多少种取的方案.

又因为相同权值的边不超过 $10$ 条, 所以直接暴搜就行了.

然后还要特判一下图不连通的情况, 输出 $0$.

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e2+7;
const int M=1e3+7;
const int mod=31011;
int n,m,fa[N],s=1,t=0,res=0,ans=1;
struct edge{
    int x,y,w;
}e[M];
int find(int x){ return x==fa[x] ?x :find(fa[x]); }
void dfs(int k){
    if(k>t){
        bool flag=1;
        for(int i=s;i<=t;i++) if(find(e[i].x)!=find(e[i].y)){ flag=0; break; }
        res=(res+flag)%mod;
        return;
    }
    int fx=find(e[k].x),fy=find(e[k].y);
    if(fx!=fy){ fa[fx]=fy; dfs(k+1); fa[fx]=fx; }
    dfs(k+1);
}
bool rule(edge a,edge b){ return a.w<b.w; }
int main(){
//  freopen("x.in","r",stdin);
//  freopen("x.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);
    for(int i=1;i<=n;i++) fa[i]=i;
    sort(e+1,e+1+m,rule);
    for(int i=1;i<=m;i=t+1){
        s=i;
        do{
            t++;
            e[t].x=find(e[t].x);
            e[t].y=find(e[t].y);
        }while(e[t+1].w==e[t].w&&t<=m);
        res=0; dfs(s); ans=ans*res%mod;
        for(int j=s;j<=t;j++) 
            if(e[j].x!=e[j].y) fa[find(e[j].x)]=find(e[j].y);
    }
    int rt=find(1);
    for(int i=2;i<=n;i++) if(find(i)!=rt) ans=0;
    printf("%d\n",ans);
    return 0;
}