题目链接：BZOJ1016-JSOI2008-最小生成树计数

题意：

给n个点，m条边，求这个图中有多少个不同的最小生成树，权值相同的边不会超过10条。

题解：

借助了两个定理：

1. 不同的最小生成树中，每种权值的边出现的次数是相同的。
2. 不同的生成树中，某一种权值的边连接完成后，形成的连通块是相同的。

这样就很简单了，只需要先做一次kruskal，计算出每种边权出现的次数，然后对于不同的边权依次进行暴搜，计算出相同边权集合中的不同解，然后乘法原理乘起来就可以了。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=31011;
int n,m,tot,cnt,ans,sum;
int f[109];
struct Edge
{
    int u,v,w;
} edge[1003];
bool cmp(Edge x,Edge y)
{
    return x.w<y.w;
}
struct data
{
    int l,r,w;
} a[1003];
int getf(int x)
{
    if(x==f[x])
        return x;
    return getf(f[x]);
}
void dfs(int x,int now,int k)
{
    if(now==a[x].r+1)
    {
        if(k==a[x].w)
            sum++;
        return;
    }
    int fx=getf(edge[now].u),fy=getf(edge[now].v);
    if(fx!=fy)
    {
        f[fx]=fy;
        dfs(x,now+1,k+1);
        f[fx]=fx;
        f[fy]=fy;
    }
    dfs(x,now+1,k);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
        f[i]=i;
    for(int i=1; i<=m; i++)
        scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
    sort(edge+1,edge+1+m,cmp);
    for(int i=1; i<=m; i++)
    {
        if(edge[i].w!=edge[i-1].w)
        {
            a[cnt].r=i-1;
            cnt++;
            a[cnt].l=i;
        }
        int fx=getf(edge[i].u),fy=getf(edge[i].v);
        if(fx!=fy)
        {
            f[fx]=fy;
            a[cnt].w++;
            tot++;
        }
    }
    a[cnt].r=m;
    if(tot!=n-1)
        return puts("0"),0;
    for(int i=1; i<=n; i++)
        f[i]=i;
    ans=1;
    for(int i=1; i<=cnt; i++)
    {
        sum=0;
        dfs(i,a[i].l,0);
        ans=(ans*sum)%mod;
        for(int j=a[i].l; j<=a[i].r; j++)
        {
            int fx=getf(edge[j].u),fy=getf(edge[j].v);
            if(fx!=fy)
                f[fx]=fy;
        }
    }
    printf("%d\n",ans);
    return 0;
}