本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-05 14:35:57

题意

题意很简单，求一个图中有多少最小生成树。

思路

试着发现一些性质，对于同一个图的两颗最小生成树，这两颗树的每种边权的边数是一样的。

证明

证明一下，考虑kruskal的过程：将所有边按照边权从小到大排序，一条一条加，如果出现环就不加。直到所有点都在一个联通块内。

如果出现环就不加这一步，也可以是如果出现环，将环上最大边权的边随机选一条边删去。所以，每种边权的边数是一样的。

注意题目中的这条要求，具有相同权值的边不会超过 10 条。 也就是说，可以暴力 $2^k$ 枚举我们加入哪些边，使得加入那些边之后最小生成树仍然合法。

合法的条件是什么？根据上面的性质，每一种边权的边数应相同，所以可以一开始跑一遍最小生成树，把每个边权在其中的出现次数预处理出来。并且加入那些边之后最小生成树不能出现环。

然后就做完了。

#include<bits\/stdc++.h>


using namespace std;

#define int long long
#define ll long long
#define Endl cout<<endl;
#define ENdl Endl
#define pii pair<int,int>
#define lowbit(x) x&(-x)
#define fi first
#define se second
#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'

const int N=2e6+10;\/\/注意修改
const int mod=31011;
const int Max=0x3f3f3f3f3f;

int n,m;
struct edge{int u,v,w;}e[N];
bool cmp(edge a,edge b){return a.w<b.w;}
map<int,int> c;\/\/每个边权在最小生成树中的出现个数
int fa[N],faa[N];
int findf(int x){return x==fa[x]?x:fa[x]=findf(fa[x]);}
int findff(int x){return x==faa[x]?x:faa[x]=findff(faa[x]);}
struct col{int l,r,w;}a[N];\/\/每个边权的出现区间
bool check(int x,int p){
    int cnt=0;
    while(x){
        if(x&1) cnt++;
        x>>=1;
    }
    return cnt!=p;
}
signed main(){
    
\/\/   freopen("a.in","r",stdin);
\/\/   freopen("a.out","w",stdout);
    fst
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e[i]={u,v,w};
    }
    for(int i=1;i<=n;i++) fa[i]=i;
    sort(e+1,e+1+m,cmp);
    int tot=0;
    for(int i=1;i<=m;i++){
        int u=findf(e[i].u),v=findf(e[i].v);
        if(u==v) continue;
        fa[v]=u;
        tot++;
        c[e[i].w]++;
    }
    if(tot!=n-1){
        cout<<0;
        return 0;
    }
    int cnt=0;
    for(int i=1;i<=m;i++){
        if(e[i].w!=e[i-1].w){
            a[cnt].r=i-1;
            a[++cnt].l=i;
            a[cnt].w=e[i].w;
        }
    }
    for(int i=1;i<=n;i++) fa[i]=faa[i]=i;
    a[cnt].r=m;
    int ans=1,sum=0;
    for(int i=1;i<=cnt;i++){
        sum=0;
        for(int k=0;k<(1<<(a[i].r-a[i].l+1));k++){
            if(check(k,c[a[i].w])) continue;
            \/\/cout<<k<<' ';
            for(int i=1;i<=n;i++) fa[i]=faa[i];
            int f=0;
            for(int j=a[i].l;j<=a[i].r;j++){
                int d=j-a[i].l;
                if((k>>d)&1){
                    int u=findf(e[j].u),v=findf(e[j].v);
                    if(u==v) f=1;
                    fa[v]=u;
                }
            }
            if(!f) sum++;
        }

        if(sum!=0) ans=(ans*sum)%mod;
        sum=0;
        for(int j=a[i].l;j<=a[i].r;j++){
            int u=findff(e[j].u),v=findff(e[j].v);
            if(u==v) continue;
            faa[v]=u;
        }
    }
    cout<<ans;
    return 0;
}