矩阵树笔记 Matrix tree

发表于2020-08-14更新于2023-09-15字数统计3.4k阅读时长35分

Matrix tree

矩阵树

定义图无向图 GG 的拉普拉斯矩阵 (Laplacian matrix) L(G)L(G)

Lij={−miji≠ j,i与j之间有mij条边deg(i)i=j,deg(i)为点i的度L_{ij} = \begin{cases} -m_{ij} & i \ne\ j, i 与 j 之间有 m_{ij}条边\\ deg(i) & i = j, deg(i) 为点 i 的度\\ \end{cases}

则 GG 的生成树个数等于 detL0detL_0，其中 L0L_0 是去掉 LL 的 第 ii 行，第 ii 列得到的子矩阵 (ii 任意)。具体证明见 参考资料。
那么就可以化矩阵 L0L_0 为上三角矩阵，即可求出 detL0detL_0。

Code

template
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
inline void add(int u, int v) { //加边
    G[u][u]++, G[v][v]++;
    G[u][v]--, G[v][u]--;
}

LL G[MAXN][MAXN];
inline LL Gauss(int tot) { //高斯消元
    LL ans = 1;
    for (int i = 1; i < tot; i++) {
        for (int j = i + 1; j < tot; j++)
            while (G[j][i]) {
                LL t = G[i][i] / G[j][i];
                for (int k = i; k < tot; k++)
                    G[i][k] = ((G[i][k] - t * G[j][k]) % MOD + MOD) % MOD;
                swap(G[i], G[j]);
                ans = -ans;
            }
        ans = ans * G[i][i] % MOD;
    }
    return (ans + MOD) % MOD;
}

变元矩阵树

用于求所有生成树边权乘积的和。和矩阵树求法相同，不过行列式中 G[i][i]G[i][i] 记录的是点 ii 所连的边权总和，G[i][j]G[i][j] 记录的是 i,ji, j 之间边权的相反数之和。

Code

tempalte
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
inline void add(int u, int v, double val) { //加边
    G[u][u] += val, G[v][v] += val;
    G[u][v] -= val, G[v][u] -= val;
}

inline double Gauss(int n) { //高斯消元
    double ans = 1;
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (fabs(G[i][i]) < eps) swap(G[i], G[j]), ans = -ans;
            else break;
        }
        for (int j = i + 1; j < n; j++) {
            if (fabs(G[j][i]) < eps) continue;
            double tmp = G[j][i] / G[i][i];
            for (int k = i; k < n; k++)
                G[j][k] -= tmp * G[i][k];
        }
        ans = ans * G[i][i];
    }
    return ans;
}

Cayley 定理

有 pp 个顶点的完全图 KpK_p，生成树的个数为 pp−2p^{p - 2} 个 (行列式递推就行了)。

图联通方案数

有 pp 个顶点的图，已知有 kk 个连通块，如果仅将连通块看作点，则对应的生成树个数为 pk−2p^{k - 2}。证明。

例题

HEOI2015 小Z的房间

Description

题目链接

Solution

模板题，不过注意不要建重边。

Code

小Z的房间
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
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

constexpr int MAXN = 2000;
constexpr int MOD = 1e9;

int n, m, tot, mp[MAXN][MAXN];

LL G[MAXN][MAXN];
inline LL Gauss() {
    LL ans = 1;
    for (int i = 1; i < tot; i++) {
        for (int j = i + 1; j < tot; j++)
            while (G[j][i]) {
                LL t = G[i][i] / G[j][i];
                for (int k = i; k < tot; k++)
                    G[i][k] = ((G[i][k] - t * G[j][k]) % MOD + MOD) % MOD;
                swap(G[i], G[j]);
                ans = -ans;
            }
        ans = ans * G[i][i] % MOD;
    }
    return (ans + MOD) % MOD;
}

inline void add(int u, int v) {
    if (u > v) return;
    G[u][u]++, G[v][v]++;
    G[u][v]--, G[v][u]--;
}

int main () {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            char ch;
            cin >> ch;
            if (ch == '.') mp[i][j] = ++tot;
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int u = mp[i][j], v;
            if (!u) continue;
            if (v = mp[i - 1][j]) add(u, v);
            if (v = mp[i + 1][j]) add(u, v);
            if (v = mp[i][j - 1]) add(u, v);
            if (v = mp[i][j + 1]) add(u, v);
        }
    cout << Gauss() << endl;
    return 0;
}

B SHOI2016 黑暗前的幻想乡

Description

题目链接

Solution

矩阵树+容斥+状态压缩。
令 PiP_i 表示事件: 第 ii 个公司没有参与修建。由容斥原理有 ∣P1‾∩P2‾∩...∩Pn−k‾∣=N−∑1<=i<=n−k∣Pi∣+∑1<=i<j<=n−k∣Pi∩Pj∣|\overline{P_1} \cap \overline{P_2} \cap ...\cap \overline{P_{n-k}}|= N-\sum\limits_{1<=i<={n-k}}|P_i|+\sum\limits_{1<=i<j<={n-k}}|P_i\cap P_j| −∑1<=i<j<q<=n−k∣Pi∩Pj∩Pq∣+...+(−1)n−k∣P1∩P2∩...∩Pn−k∣-\sum\limits_{1<=i<j<q<={n-k}}|P_i\cap P_j\cap P_q|+...+(-1)^{n-k}|P_1\cap P_2 \cap ...\cap P_{n-k}|。压缩公司的参与状态即可。

Code

黑暗前的幻想乡
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
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

constexpr int MOD = 1e9 + 7;

int n, m, tot;
vector<pair<int, int>> vec[20];

LL G[20][20];
inline LL Gauss() {
    LL ans = 1;
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j < n; j++)
            while (G[j][i]) {
                LL t = G[i][i] / G[j][i];
                for (int k = i; k < n; k++)
                    G[i][k] = ((G[i][k] - t * G[j][k]) % MOD + MOD) % MOD;
                swap(G[i], G[j]);
                ans = -ans;
            }
        ans = ans * G[i][i] % MOD;
    }
    return (ans + MOD) % MOD;
}

inline void add(int u, int v) {
    G[u][u]++, G[v][v]++;
    G[u][v]--, G[v][u]--;
}

int main () {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 0, cnt; i < n - 1; i++) {
        cin >> cnt;
        for (int j = 1, u, v; j <= cnt; j++) {
            cin >> u >> v;
            vec[i].emplace_back(u, v);
        }
    }
    LL ans = 0;
    for (int st = 0; st < (1 << (n - 1)); st++) {
        int cnt = 0;
        memset(G, 0, sizeof(G));
        for (int i = 0; i < n - 1; i++)
            if (st & (1 << i)) {
                for (auto& e : vec[i])
                    add(e.first, e.second);
                cnt++;
            }
        if ((n - cnt - 1) & 1) ans = (ans - Gauss()) % MOD;
        else ans = (ans + Gauss()) % MOD;
    }
    cout << (ans + MOD) % MOD << endl;
    return 0;
}

C SDOI2014 重建

Description

题目链接

Solution

我们已知变元矩阵树可以求 ∑T∏e∈Tpe\sum_T \prod_{e \in T} p_e。
而本题需要求 ∑T{∏e∈Tpe∏e∉T(1−pe)}\sum_T \{ \prod_{e \in T} p_e \prod_{e \notin T} (1 - p_e) \}。变换可得：

∑T{∏e∈Tpe∏e∉T(1−pe)}\sum_T \{ \prod_{e \in T} p_e \prod_{e \notin T} (1 - p_e) \}

=∑T{∏e∈Tpe∏e(1−pe)∏e∈T(1−pe)}= \sum_T \{ \prod_{e \in T} p_e \frac{\prod_e (1 - p_e)}{\prod_{e \in T} (1-p_e)} \}

=∏e(1−pe)(∑T∏e∈Tpe1−pe)= \prod_e (1 - p_e) (\sum_T \prod_{e \in T} \frac{p_e}{1-p_e})

然后以 pe1−pe\frac{p_e}{1 - p_e} 为边权使用变元矩阵树求边权积的和即可。

Code

重建
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
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

int n;
double ans(1), eps = 1e-8;

double G[55][55], p[55][55];
inline double Gauss() {
    double ans = 1;
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (fabs(G[i][i]) < eps) swap(G[i], G[j]), ans = -ans;
            else break;
        }
        for (int j = i + 1; j < n; j++) {
            if (fabs(G[j][i]) < eps) continue;
            double tmp = G[j][i] / G[i][i];
            for (int k = i; k < n; k++)
                G[j][k] -= tmp * G[i][k];
        }
        ans = ans * G[i][i];
    }
    return ans;
}

inline void add(int u, int v, double val) {
    G[u][u] += val, G[v][v] += val;
    G[u][v] -= val, G[v][u] -= val;
}

int main () {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cout << setprecision(4) << fixed;
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            cin >> p[i][j];
            if (i >= j) continue;
            double tmp = fabs(1.0 - p[i][j]) < eps ? eps : fabs(1.0 - p[i][j]);
            ans *= tmp, p[i][j] /= tmp;
            add(i, j, p[i][j]);
        }
    cout << ans * fabs(Gauss()) << endl;
    return 0;
}

D HDU多校 Expectation

Description

题目链接
求生成树边权按位与的期望。

Solution

期望 = 按位与的和 / 总生成树个数。生成树个数可以用矩阵树求出。对于按位与，考虑每一位，如果生成树边权的第 bitbit 位全为 1，则 bitbit 位的按位与为1，否则为0。相当于0, 1的乘积。于是可对每一位跑变元矩阵树，最后按位累加即为按位与的和。

Code Expectation

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
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

constexpr int MAXN = 300;
constexpr LL INF = 1e16;
constexpr LL MOD = 998244353;

int t, n, m;

inline LL qpow(LL a, LL b) {
    LL res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

LL K[110][110], K2[32][110][110];
LL gauss(int n) {  //求矩阵K的n-1阶顺序主子式
    LL res = 1;
    for (int i = 1; i <= n - 1; i++) {  //枚举主对角线上第i个元素
        for (int j = i + 1; j <= n - 1; j++) {  //枚举剩下的行
            while (K[j][i]) {                   //辗转相除
                int t = K[i][i] / K[j][i];
                for (int k = i; k <= n - 1; k++)  //转为倒三角
                    K[i][k] = (K[i][k] - t * K[j][k] + MOD) % MOD;
                swap(K[i], K[j]);  //交换i、j两行
                res = -res;        //取负
            }
        }
        res = (res * K[i][i]) % MOD;
    }
    return (res + MOD) % MOD;
}

LL gauss2(int n, int bit) {  //求矩阵K的n-1阶顺序主子式
    LL res = 1;
    for (int i = 1; i <= n - 1; i++) {  //枚举主对角线上第i个元素
        for (int j = i + 1; j <= n - 1; j++) {  //枚举剩下的行
            while (K2[bit][j][i]) {                   //辗转相除
                int t = K2[bit][i][i] / K2[bit][j][i];
                for (int k = i; k <= n - 1; k++)  //转为倒三角
                    K2[bit][i][k] = (K2[bit][i][k] - t * K2[bit][j][k] + MOD) % MOD;
                swap(K2[bit][i],K2[bit][j]);  //交换i、j两行
                res = -res;        //取负
            }
        }
        res = (res * K2[bit][i][i]) % MOD;
    }
    return (res + MOD) % MOD;
}

int main() {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> t;
    while (t--) {
        memset(K, 0, sizeof(K));
        memset(K2, 0, sizeof(K2));
        cin >> n >> m;
        LL ans = 0;
        for (int i = 1, u, v, w; i <= m; i++) {
            cin >> u >> v >> w;
            for (int j = 0; j < 31; j++) {
                int tmp = (w & (1 << j));
                if (tmp) {
                    K2[j][u][u]++, K2[j][v][v]++;
                    K2[j][u][v]--, K2[j][v][u]--;
                }
            }
            K[u][u]++, K[v][v]++;
            K[u][v]--, K[v][u]--;
        }
        LL fenMu = gauss(n);
        for (int i = 0; i < 31; i++) {
            ans = (ans + ((gauss2(n, i) << i) % MOD)) % MOD;
        }
        cout << ans * qpow(fenMu, MOD - 2) % MOD << "\n";
    }
    return 0;
}

E 最小生成树计数

Description

题目链接

Solution

最小生成树有一个性质是，同一边权的边的数目是相同的。考虑先随意生成一个最小生成树，然后对生成树上的每个权值计算贡献 (相同边权只计算一次)。
具体来说，就是枚举最小生成树上的边，将其删除 (设边权为 wiw_i，相同边权只删除一次)，然后得到若干连通块 (缩成一个点)。再用所有边权为 wiw_i 的边把连通块连接起来，对这些连通块的生成树计数，最后乘法原理得到最终答案。

Code

最小生成树计数
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
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

constexpr int MAXN = 105;
constexpr int MOD = 31011;

int n, m, ans = 1, fa[MAXN], vis[MAXN], belong[MAXN];
vector<pair<int, pair<int, int>>> vec, eTree;

inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

inline void Union(int a, int b) {
    int r1 = find(a), r2 = find(b);
    if (r1 != r2) fa[r1] = r2;
}

inline void kruskal(int cnt = 0) {
    for (int i = 1; i <= n; i++) fa[i] = i;
    sort(vec.begin(), vec.end());
    for (auto& e : vec) {
        int w = e.first, u = e.second.first, v = e.second.second;
        if (find(u) != find(v)) {
            cnt++;
            Union(u, v);
            eTree.push_back(make_pair(w, make_pair(u, v)));
        }
        if (cnt == n - 1) break;
    }
}

int G[MAXN][MAXN];
inline LL Gauss(int n) {
    LL ans = 1;
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j < n; j++)
            while (G[j][i]) {
                LL t = G[i][i] / G[j][i];
                for (int k = i; k < n; k++)
                    G[i][k] = ((G[i][k] - t * G[j][k]) % MOD + MOD) % MOD;
                swap(G[i], G[j]);
                ans = -ans;
            }
        ans = ans * G[i][i] % MOD;
    }
    return (ans + MOD) % MOD;
}

inline void add(int u, int v) { G[u][u]++, G[v][v]++, G[u][v]--, G[v][u]--; }

inline int calc(int res = 1) {
    for (int i = 0; i < eTree.size(); i++) {
        if (i && eTree[i - 1].first == eTree[i].first) continue;
        int cnt = 0;
        memset(G, 0, sizeof(G)), memset(vis, 0, sizeof(vis));
        for (int j = 1; j <= n; j++) fa[j] = j;
        for (auto& e : eTree) { //生成树上权值不为eTree[i]的边，求出联通块
            int w = e.first, u = e.second.first, v = e.second.second;
            if (w == eTree[i].first) continue;
            Union(u, v);
        }
        for (int j = 1; j <= n; j++) {//处理连通块数目 方便后续生成树Gauss计数
            if (!vis[find(j)]) vis[find(j)] = ++cnt;
            belong[j] = vis[find(j)];
        }
        for (auto& e : vec) { //所有边，将连通块相连
            int w = e.first, u = e.second.first, v = e.second.second;
            if (w != eTree[i].first) continue;
            add(belong[u], belong[v]); //加边
        }
        res = res * Gauss(cnt) % MOD;
    }
    return res;
}

int main () {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        vec.push_back(make_pair(w, make_pair(u, v)));
    }
    kruskal();
    cout << calc() << endl;
    return 0;
}

有向图的有根最小生成树计数

Description

题目链接

Solution

求以 1 为根的生成树数量。
构造矩阵 AA： i!=ji != j，aija_{ij} 表示 ii 到 jj 的有向边数的相反数；aiia_{ii} 为 ii 的出度。
该矩阵去掉第 1 行，第 1 列即为以 1 为根的生成树数量。

Code

CQOI2018 社交网络
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
#include <bits/stdc++.h>

using namespace std;

constexpr int MAXN = 1e3 + 3, MOD = 1e4 + 7;

int n, m, u, v;

int G[MAXN][MAXN];
inline int Gauss(int n, int res = 1) {
    for (int i = 2; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            while (G[j][i]) {
                int t = G[i][i] / G[j][i];
                for (int k = i; k <= n; k++)
                    G[i][k] = ((G[i][k] - t * G[j][k]) % MOD + MOD) % MOD;
                swap(G[i], G[j]);
                res = -res;
            }
        }
        res = res * G[i][i] % MOD;
    }
    return (res + MOD) % MOD;
}
/*从 u 到 v 的有向边*/
inline void add(int u, int v) { G[u][v]--, G[u][u]++; }

signed main() {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    while (m--) cin >> u >> v, add(u, v);
    cout << Gauss(n) << endl;
    return 0;
}