题目链接：HDU4408-Minimum Spanning Tree

题意：

给n个点，m条边，求这个图中有多少个不同的最小生成树。

题解：

借助了两个定理：

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

因为权值相同的边的数量未知，所以只能用矩阵树定理去算。

对于权值相同的边，用矩阵树定理算出能够构成的最小生成树的数量，最后乘起来即可。

矩阵树定理：

1. 记图的度数矩阵为A1(G)，大小为n×n，i!=j时的元素为0，i=j时的元素为该点的度数。
2. 记图的邻接矩阵为A2(G)，大小为n×n，A2(i)(j)表示i与j两个点连通。
3. 由以上两个矩阵可以构造出Kirchhoff矩阵：A(G)=A1(G)-A2(G)。
4. 生成树的数量等于该Kirchhoff矩阵任何一个n-1阶柱子式的行列式的绝对值。

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=500;
const int MAXM=5000;
int n,m;
ll ans,sum,mod;
int fa[MAXN],ka[MAXN],used[MAXN];
ll mp[MAXN][MAXN],mat[MAXN][MAXN];
vector<int> gra[MAXN];
struct Edge
{
    int u,v,w;
} edge[1009];
bool cmp(Edge x,Edge y)
{
    return x.w<y.w;
}
int getf(int x,int father[])
{
    if(x==father[x])
        return x;
    return father[x]=getf(father[x],father);
}
ll det(ll a[][MAXN],int n)
{
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            a[i][j]%=mod;
    ll ret=1;
    for (int i=1; i<n; i++)
    {
        for (int j=i+1; j<n; j++)
            while (a[j][i])
            {
                ll t=a[i][i]/a[j][i];
                for (int k=i; k<n; k++)
                    a[i][k]=(a[i][k]-a[j][k]*t)%mod;
                for (int k=i; k<n; k++)
                    swap(a[i][k],a[j][k]);
                ret=-ret;
            }
        if (a[i][i]==0)
            return 0;
        ret=ret*a[i][i]%mod;
    }
    return (ret+mod)%mod;
}
void matrix_tree()
{
    for(int i=1; i<=n; i++)
        if(used[i])
        {
            gra[getf(i,ka)].push_back(i);
            used[i]=0;
        }
    for(int k=1; k<=n; k++)
    {
        if(gra[k].size()>1)
        {
            memset(mat,0,sizeof(mat));
            int len=gra[k].size();
            for(int i=0; i<len; i++)
                for(int j=i+1; j<len; j++)
                {
                    int li=gra[k][i],lj=gra[k][j];
                    mat[j][i]-=mp[li][lj];
                    mat[i][j]=mat[j][i];
                    mat[i][i]+=mp[li][lj];
                    mat[j][j]+=mp[li][lj];
                }
            sum=det(mat,len);
            sum%=mod;
            ans=(ans%mod*sum%mod)%mod;
            for(int i=0; i<len; i++)
                fa[gra[k][i]]=k;
        }
    }
    for(int i=1; i<=n; i++)
    {
        fa[i]=ka[i]=getf(i,fa);
        gra[i].clear();
    }
}
int main()
{
    while(scanf("%d%d%lld",&n,&m,&mod)==3)
    {
        if(n==0&&m==0&&mod==0)
            return 0;
        memset(mp,0,sizeof(mp));
        memset(used,0,sizeof(used));
        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<=n; i++)
        {
            fa[i]=ka[i]=i;
            gra[i].clear();
        }
        int temp=edge[1].w;
        ans=1;
        for(int i=1; i<=m; i++)
        {
            int fx=getf(edge[i].u,fa);
            int fy=getf(edge[i].v,fa);
            if(fx!=fy)
            {
                used[fx]=used[fy]=1;
                ka[getf(fx,ka)]=getf(fy,ka);
                mp[fx][fy]++;
                mp[fy][fx]++;
            }
            if(i==m||edge[i+1].w!=temp)
            {
                matrix_tree();
                temp=edge[i+1].w;
            }
        }
        bool flag=1;
        for(int i=2; i<=n; i++)
            if(ka[i]!=ka[i-1])
            {
                flag=0;
                puts("0");
                break;
            }
        if(flag)
            printf("%lld\n",ans%mod);
    }
    return 0;
}