Matrix-Tree

BZOJ 4031 小Z的房间

Posted on

矩阵树定理第二题,用于有取模处理的运算。
中间一直超时,还一位bzoj会卡宏定义……真是石乐志

题意:
给你一个n×m矩阵,矩阵中的' . '表示成一个房间,' * ‘ 表示柱子,在相邻的房间中可以连边,要求每个房间都相连,求方案数。

思路:
算是比较裸的矩阵树定理应用了,对每一个点,标号,再对相邻都是点的格子建边。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)

typedef long long ll;
const int maxn = 105;
const int mod = 1e9;

ll c[maxn][maxn];
char mat[maxn][maxn];
int G[maxn][maxn];
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, -1, 0, 1 };

ll getDet(ll a[][maxn], int n)
{
    range(i, 1, n) range(j, 1, n) a[i][j] = (a[i][j] + mod) % mod;
    ll ret = 1;
    range(i, 1, n - 1)
    {
        range(j, i + 1, n - 1) while (a[j][i])
        {
            ll t = a[i][i] / a[j][i];
            range(k, i, n - 1) a[i][k] = (a[i][k] - a[j][k] * t % mod + mod) % mod;
            range(k, i, n - 1) 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;
}

int main()
{
    int n, m, num = 0;
    scanf("%d %d", &n, &m);
    each(i, n) scanf("%s", mat[i]);
    each(i, n) each(j, m) if (mat[i][j] == '.') G[i][j] = ++num;
    each(i, n) each(j, m) if (G[i][j])
    {
        int u = G[i][j];
        each(k, 4)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x < 0 || x >= n || y < 0 || y >= m || mat[x][y] != '.')
                continue;
            int v = G[x][y];
            c[u][u]++, c[u][v]--;
        }
    }
    printf("%lld\n", getDet(c, num));
    return 0;
}
Maths

SPOJ 104 Highways

Posted on

早上在学最小生成树计数。
最小生成树算法基于 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;
}