SPOJ 104 Highways

早上在学最小生成树计数。
最小生成树算法基于 Matrix-Tree 定理，Matrix-Tree定理是被广泛应用与求生成树计数中。
其具体流程为构造基尔霍夫矩阵，再对其求 n-1 阶行列式即可。

• 基尔霍夫矩阵 为 其度数矩阵D[G] – 邻接矩阵A[G]
• 度数矩阵D[G] 满足，当 i≠ j 时,dij=0；当i=j时，dij等于vi的度数。
• 邻接矩阵A[G] 满足，如果vi、vj之间有边直接相连，则aij=1，否则为0。

不得不说SPOJ的数据之强，一个小问题找了我大半天才找着，SPOJ倒是我想做验证模板的不二之选。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define ll long long

using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 105;

ll c[maxn][maxn];
ll degree[maxn];

inline bool scan_d(int& num)
{
    char in;
    in = getchar();
    if (in == EOF)
        return false;
    while (in < '0' || in > '9')
        in = getchar();
    num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9')
        num *= 10, num += in - '0';
    return true;
}

ll getDet(ll a[][maxn], int n)
{
    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);
                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];
    }
    return ret < 0 ? -ret : ret;
}

int main()
{
    int T, u, v, n, m;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        memset(c, 0, sizeof c);
        memset(degree, 0, sizeof degree);
        while (m--) {
            scan_d(u);
            scan_d(v);
            c[u][v] = c[v][u] = -1;
            degree[u]++, degree[v]++;
        }
        for (int i = 1; i <= n; i++)
            c[i][i] = degree[i]; //因为不存在自环呀
        printf("%lld\n", getDet(c, n - 1));
    }
    return 0;
}