解題區/解題區 - UVa

UVa 10766 - Organising the Organisation

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給定組織每個人的關係圖，(x, y) 之間若有邊，表示彼此之間不能互為上司和下屬關係，請問將組織變成樹狀階層關係，總共有多少種方式。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
5 5 2
3 1
3 4
4 5
1 4
5 3
4 1 1
1 4
3 0 2

Sample Output

1
2
3
3
8
3

Solution

先把沒有邊變成有邊、有邊變成沒邊，接著找到有多少種生成樹。

利用 Kirchhoff’s theorem 來完成，證明看 wiki。

先將鄰接矩陣轉換成拉普拉斯矩陣 L (Laplacian matrix)，其對角線上是每一個節點的度數，若 (x, y) 之間有邊，則標記 -1。接著將矩陣 L 去掉其中一行或一列，計算 L* 的行列值就是生成樹個數。

實際上拉普拉斯矩陣 L 可以被表示成 incidence matrix E (行: 頂點 x, 列: 邊編號 e)，$L = EE^T$。令 F 為 E 刪除第一行 (row) 的結果，則 $M_{11} = FF^T$，藉由 Cauchy–Binet formula 進行行列式展開，會從 m 條邊抓 n-1 條邊出來，拆分成 $\binom{m}{n-1}$ 項，對於每一項的結果，若圖連通則行列式為 1，反之為 0。

數學真奇妙！不要問，這真的很可怕。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
// Kirchhoff's theorem, Matrix Tree Theorem, determinant value
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
// const long long PRIME_MOD = 1000000007LL;
const long long PRIME_MOD = 1000000000000037LL; // > 1e+15
const int MAXN = 64;
long long Q[MAXN][MAXN] = {}, L[MAXN][MAXN] = {};
int cg[MAXN][MAXN];
long long mul(long long a, long long b, long long mod) {
    if (b < 0)
        return -mul(a, -b, mod);
    long long ret = 0;
    for ( ; b != 0; b>>=1, (a<<=1)%=mod)
        if (b&1) (ret += a) %= mod;
    return ret;
}
// ax + by = g
void exgcd(long long x, long long y, long long &g, long long &a, long long &b) {
    if (y == 0)
        g = x, a = 1, b = 0;
    else
        exgcd(y, x%y, g, b, a), b -= (x/y) * a;
}
long long llabs(long long x) {
    return x < 0 ? -x : x;
}
long long det(long long A[][MAXN], int n) {
    long long sum = 1;
    long long g, a, b;
    for (int i = 0; i < n; i++) {
        exgcd(A[i][i], PRIME_MOD, g, a, b);
        long long inv = a;
        if (g < 0)  inv = -inv;
        for (int j = i+1; j < n; j++) {
            for (int k = n - 1; k >= i; k--) {
                A[j][k] = A[j][k] - mul(mul(A[i][k], A[j][i], PRIME_MOD), inv, PRIME_MOD);
                A[j][k] = (A[j][k]%PRIME_MOD + PRIME_MOD) %PRIME_MOD;
            }
        }
        sum = mul(sum, A[i][i], PRIME_MOD);
        if (sum == 0)
            return 0;
    }
    if (sum < 0)    sum = (sum % PRIME_MOD + PRIME_MOD) %PRIME_MOD;
    return llabs(sum);
}
int main() {
//    long long g, a, b, llx = 70, lly = 11;
//    exgcd(llx, lly, g, a, b);
//    printf("%lld %lld + %lld %lld = %lld\n", llx, a, lly, b, g);
    int N, M, K;
    int x, y;
    while (scanf("%d %d %d", &N, &M, &K) == 3) {
        memset(cg, 0, sizeof(cg));
        memset(Q, 0, sizeof(Q));
        memset(L, 0, sizeof(L));
        
        for (int i = 0; i < M; i++) {
            scanf("%d %d", &x, &y);
            x--, y--;
            cg[x][y] = cg[y][x] = 1;
        }
        
        // construct the Laplacian matrix Q
        for (int i = 0; i < N; i++) {
            int deg = 0;
            for (int j = 0; j < N; j++) {
                if (i != j && cg[i][j] == 0)  // has edge
                    Q[i][j] = -1, deg++;
            }
            Q[i][i] = deg;
        }
        
        // deleting row 1 and column 1 yields
        for (int i = 1; i < N; i++)
            for (int j = 1; j < N; j++)
                L[i-1][j-1] = Q[i][j];
        
        printf("%lld\n", det(L, N-1));
    }
    return 0;
}
/*
 5 5 2
 3 1
 3 4
 4 5
 1 4
 5 3
 
 4 1 1
 1 4
 
 3 0 2
 
 */