UVA 10766 Organising the Organisation(Count spanning tree)

Description

给出N个点的无向图的补图，求原图最小生成树的数目

Analyze

可证的事实：如果图G是一棵树，那么它的Kirchhoff矩阵的每一个n - 1阶主子式的行列式都是1。

推理：如果图G包含X棵树，那么它的Kirchhoff矩阵的每一个n - 1阶主子式的行列式都包含X个1，即X

另外解行列式采用高斯消元(转为上三角行列式)，与线性代数课上所学的方法有点差异，课上的方法直接了当，前面的行不变，处理后面的行，使得下三角逐渐变为全0(从左至右，从上到下)，但会出现小数。为了避免出现小数，采用如下方法：将“首 需处理 行”与“目标行”运算，使首非零元变0，然后交换两行。由于“首 需处理 行”首非零元总是 >= “目标行”首非零元，因此不会出现小数。

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
const int N = 55;

int n, m, K;
ll a[N][N], b[N][N];

ll Gauss()
{
    ll res = 1;
    ///i start from 2 : throw away first row and first column
    for(int i = 2; i <= n; ++i)
    {
        for(int j = i + 1; j <= n; ++j)
        {
            while(b[j][i])///turn first not 0 element in row[j] into 0
            {
                ll t = b[i][i] / b[j][i];
                for(int k = i; k <= n; ++k)
                    b[i][k] -= b[j][k] * t;
                for(int k = i; k <= n; ++k)
                    swap(b[i][k], b[j][k]);
                res *= -1;///Don't forget it!
            }
        }
        if(b[i][i] == 0)
            return 0;
        res *= b[i][i];
    }
    return res > 0 ? res : -res;
}

int main()
{
    while(~scanf("%d %d %d", &n, &m, &K))
    {
        memset(a, 0,sizeof(a));
        memset(b, 0,sizeof(b));
        int u, v;
        while(m--)
        {
            scanf("%d %d", &u, &v);
            a[u][v] = a[v][u] = 1;
        }
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                if(i != j && !a[i][j])
                    b[i][i]++, b[i][j]--;
        cout << Gauss() << '\n';
    }
    return 0;
}

https://github.com/fireworks99/Documents/blob/master/%E5%91%A8%E5%86%AC%E3%80%8A%E7%94%9F%E6%88%90%E6%A0%91%E7%9A%84%E8%AE%A1%E6%95%B0%E5%8F%8A%E5%85%B6%E5%BA%94%E7%94%A8%E3%80%8B.pdf

周冬《生成树的计数及其应用》