hdoj 4408 Minimum Spanning Tree 求最小生成樹的數目

/* 
 *算法引入： 
 *給定一個含有N個結點M條邊的無向圖,求它最小生成樹的個數t(G); 
 * 
 *算法思想： 
 *抛開“最小”的限制不看,如果隻要求求出所有生成樹的個數,是可以利用Matrix-Tree定了解決的; 
 *Matrix-Tree定理此定理利用圖的Kirchhoff矩陣,可以在O(N3)時間内求出生成樹的個數; 
 * 
 *kruskal算法： 
 *将圖G={V,E}中的所有邊按照長度由小到大進行排序,等長的邊可以按照任意順序; 
 *初始化圖G’為{V,Ø},從前向後掃描排序後的邊,如果掃描到的邊e在G’中連接配接了兩個相異的連通塊,則将它插入G’中; 
 *最後得到的圖G’就是圖G的最小生成樹; 
 * 
 *由于kruskal按照任意順序對等長的邊進行排序,則應該将所有長度為L0的邊的處理當作一個階段來整體看待; 
 *令kruskal處理完這一個階段後得到的圖為G0,如果按照不同的順序對等長的邊進行排序,得到的G0也是不同; 
 *雖然G0可以随排序方式的不同而不同,但它們的連通性都是一樣的,都和F0的連通性相同(F0表示插入所有長度為L0的邊後形成的圖); 
 * 
 *在kruskal算法中的任意時刻,并不需要關注G’的具體形态,而隻要關注各個點的連通性如何(一般是用并查集表示); 
 *是以隻要在掃描進行完第一階段後點的連通性和F0相同,且是通過最小代價到達這一狀态的,接下去都能找到最小生成樹; 
 * 
 *經過上面的分析,可以看出第一個階段和後面的工作是完全獨立的; 
 *第一階段需要完成的任務是使G0的連通性和F0一樣,且隻能使用最小的代價; 
 *計算出這一階段的方案數,再乘上完成後續事情的方案數,就是最終答案; 
 * 
 *由于在第一個階段中,選出的邊數是一定的,所有邊的長又都為L0; 
 *是以無論第一個階段如何進行代價都是一樣的,那麼隻需要計算方案數就行了; 
 *此時Matrix-Tree定理就可以派上用場了,隻需對F0中的每一個連通塊求生成樹個數再相乘即可; 
 * 
 *Matrix-Tree定理: 
 *G的所有不同的生成樹的個數等于其Kirchhoff矩陣C[G]任何一個n-1階主子式的行列式的絕對值； 
 *n-1階主子式就是對于r(1≤r≤n),将C[G]的第r行,第r列同時去掉後得到的新矩陣,用Cr[G]表示; 
 * 
 *算法舉例： 
 *HDU4408(Minimum Spanning Tree) 
 * 
 *題目位址： 
 *http://acm.hdu.edu.cn/showproblem.php?pid=4408 
 * 
 *題目大意： 
 *給定一個含有N個結點M條邊的無向圖,求它最小生成樹的個數,所得結果對p取模; 
**/  
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;

const int N=111;
const int M=1111;

typedef long long ll;

struct Edges {
    int a, b, c;
    bool operator < (const Edges & x) const {
        return c < x.c;
    }
} edge[M];

int n, m;
int mod;
ll f[N], U[N], vist[N];//f,U都是并查集，U是每組邊臨時使用
ll G[N][N], C[N][N];//G頂點之間的關系，C為生成樹計數用的Kirchhoff矩陣

vector<int>V[N];//記錄每個連通分量

int Find(int x, ll f[]){
    if(x == f[x])
        return x;
    else
        return Find(f[x],f);
}

ll det(ll a[][N], int n)//生成樹計數:Matrix-Tree定理
{
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            a[i][j] %= mod;
    int ret = 1;
    for(int i = 1; i < n; i++) {
        for(int j = i+1; j < n; j++)
            while(a[j][i]) {
                int 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 Solve() {
    sort(edge, edge+m);//按權值排序
    for(int i = 1; i <= n; i++) {//初始化并查集
        f[i] = i;
        vist[i] = 0;
    }
    ll Edge = -1;//記錄相同的權值的邊
    ll ans = 1;
    for(int k = 0; k <= m; k++) {
        if(edge[k].c != Edge || k == m) {//一組相等的邊,即權值都為Edge的邊加完
            for(int i = 1; i <= n; i++) {
                if(vist[i]) {
                    ll u = Find(i,U);
                    V[u].push_back(i);
                    vist[i] = 0;
                }
            }
            for(int i = 1; i <= n; i++) {//枚舉每個連通分量
                if(V[i].size() > 1) {
                    for(int a = 1; a <= n; a++)
                        for(int b = 1; b <= n; b++)
                            C[a][b] = 0;
                    int len = V[i].size();
                    for(int a = 0; a < len; a++) //建構Kirchhoff矩陣C
                        for(int b = a+1; b < len; b++) {
                            int a1 = V[i][a];
                            int b1 = V[i][b];
                            C[b][a] -= G[a1][b1];
                            C[a][b] = C[b][a];
                            C[a][a] += G[a1][b1];//連通分量的度
                            C[b][b] += G[a1][b1];
                        }
                    ll ret = (ll)det(C,len);
                    ans = (ans*ret) % mod;
                    //對V中的每一個連通塊求生成樹個數再相乘
                    for(int a = 0; a < len; a++)
                        f[V[i][a]] = i;
                }
            }
            for(int i = 1; i <= n; i++) {
                U[i] = f[i] = Find(i,f);
                V[i].clear();
            }
            if(k == m)
                break;
            Edge = edge[k].c;
        }

        int a = edge[k].a;
        int b = edge[k].b;
        int a1 = Find(a,f);
        int b1 = Find(b,f);
        if(a1 == b1)
            continue;
        vist[a1] = vist[b1] = 1;
        U[Find(a1,U)] = Find(b1,U);//并查集操作
        G[a1][b1]++;
        G[b1][a1]++;
    }

    int flag = 0;
    for(int i = 2; i <= n && !flag; i++) {
        if(U[i] != U[i-1]) flag = 1;
    }
    if(m == 0) flag = 1;
    printf("%I64d\n", flag ? 0 : ans%mod);
}

int main() {
    while(~scanf("%d%d%d", &n, &m, &mod) && n+m+mod) {
        memset(G, 0, sizeof(G));
        for(int i = 1; i <= n; i++)
            V[i].clear();
        for(int i = 0; i < m; i++)
            scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].c);
        Solve();
    }
    return 0;
}