题目

题解：

题解
就是不同的最小生成树方案，每种权值的边的数量是确定的，每种权值的边的作用是确定的
排序以后先做一遍最小生成树，得出每种权值的边使用的数量x
然后对于每一种权值的边搜索，得出每一种权值的边选择方案
根据乘法原理计数

标程：

#include<bits/stdc++.h>
using namespace std;
const int M=31011;
struct node{
    int x,y,w;
}e[1002];
int fa[102],n,m,i,j,sum,ans,cnt,l[1002],r[1002],num[1002],rx,ry,tot;
bool cmp(node x,node y){
    return x.w<y.w;
}
int find(int x){
    return x==fa[x]?x:find(fa[x]);//合并连通块时压缩就不能方便地分开连通块
}
void dfs(int x,int now,int k){
    if (now>r[x]){
        if (k==num[x]) sum++;
        return;
    }
    int rx=find(e[now].x),ry=find(e[now].y);
    if (rx!=ry){
        fa[rx]=ry;
        dfs(x,now+1,k+1);
        fa[rx]=rx;fa[ry]=ry;
    }
    dfs(x,now+1,k);
}
int main(){
    scanf("%d%d",&n,&m);
    for  (i=1;i<=n;i++) fa[i]=i;
    for (i=1;i<=m;i++) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);
    sort(e+1,e+m+1,cmp);
    for (i=1;i<=m;i++){
        if (e[i].w!=e[i-1].w) r[cnt]=i-1,l[++cnt]=i;
        rx=find(e[i].x);ry=find(e[i].y);
        if (rx!=ry) fa[rx]=ry,tot++,num[cnt]++;
    }
    if (tot<n-1){
        printf("0");
        return 0;
    }
    for (i=1;i<=n;i++) fa[i]=i;//重新赋值
    r[cnt]=m;ans=1;
    for (i=1;i<=cnt;i++){
        sum=0;
        dfs(i,l[i],0);
        ans=ans*sum%M;
        for (j=l[i];j<=r[i];j++){
            rx=find(e[j].x);ry=find(e[j].y);
            if (rx!=ry) fa[rx]=ry;
        }
    }
    printf("%d",ans);
}