Day 018-Q4 — 行列木定理（Kirchhoff's Theorem）

2026-05-01 赤色 Master / Phase 8+ ★★★★★★★★★ Matrix Tree Theorem

問題

N頂点M辺の無向グラフ G が与えられる。G の全域木の数を $10^9+7$ で割った余りを求めよ。各辺に重み $w_e$ が付いている場合、重み付き全域木の総数も求めよ。

制約

$2 \le N \le 400$
$0 \le M \le N(N-1)/2$
重み $w \le 10^9$

入出力例

入力例 1

4 5
1 2 1
1 3 2
1 4 3
2 3 4
3 4 5

出力例 1

8

ヒント (段階的開示)

ヒント1: 方向性
行列木定理：グラフのラプラシアン行列 L の任意の (N-1)×(N-1) 余因子の行列式が全域木の数。
ヒント2: アプローチ
L = D - A を構築。1行1列削除した行列の行列式を Gaussian elimination + modular inverse で計算。重み付きの場合、A[i][j] = w_{ij}, D[i][i] = Σ w_{ij}。
ヒント3: 誘導 
def det(mat, mod):
    n = len(mat)
    result = 1
    for i in range(n):
        # ピボット選択 → スワップ → 消去
        ...
    return result

模範解答 (Python)

import sys
input = sys.stdin.readline

MOD = 10**9 + 7

def det_mod(mat, mod):
    n = len(mat)
    mat = [row[:] for row in mat]
    result = 1
    for i in range(n):
        pivot = -1
        for j in range(i, n):
            if mat[j][i] % mod != 0:
                pivot = j; break
        if pivot == -1:
            return 0
        if pivot != i:
            mat[i], mat[pivot] = mat[pivot], mat[i]
            result = (-result) % mod
        result = result * mat[i][i] % mod
        inv = pow(mat[i][i], mod-2, mod)
        for j in range(i+1, n):
            if mat[j][i] == 0: continue
            factor = mat[j][i] * inv % mod
            for k in range(i, n):
                mat[j][k] = (mat[j][k] - factor * mat[i][k]) % mod
    return result % mod

def main():
    N, M = map(int, input().split())
    edges = []
    for _ in range(M):
        u, v, w = map(int, input().split())
        u -= 1; v -= 1
        edges.append((u, v, w))

    L = [[0]*N for _ in range(N)]
    for u, v, w in edges:
        L[u][u] = (L[u][u] + 1) % MOD
        L[v][v] = (L[v][v] + 1) % MOD
        L[u][v] = (L[u][v] - 1) % MOD
        L[v][u] = (L[v][u] - 1) % MOD
    cofactor = [row[:N-1] for row in L[:N-1]]
    spanning_trees = det_mod(cofactor, MOD)
    print(spanning_trees)

    Lw = [[0]*N for _ in range(N)]
    for u, v, w in edges:
        Lw[u][u] = (Lw[u][u] + w) % MOD
        Lw[v][v] = (Lw[v][v] + w) % MOD
        Lw[u][v] = (Lw[u][v] - w) % MOD
        Lw[v][u] = (Lw[v][u] - w) % MOD
    cofactor_w = [row[:N-1] for row in Lw[:N-1]]
    weighted_sum = det_mod(cofactor_w, MOD)
    print(weighted_sum)

main()

Step-by-Step 解説

1ラプラシアン行列の構築
L = D - A。D[i][i] = 頂点 i の次数、A[i][j] = i-j 間に辺があれば1。重み付きは辺の重みを使う。
2余因子行列
任意の1行1列（通常は0行0列）を削除した (N-1)×(N-1) 行列を使う。どの行列を削除しても行列式は同じ。
3行列式の計算（Gaussian elimination mod p）
ガウス消去法で上三角化し、対角成分の積。mod p での各ステップで逆元を使う。
4重み付き全域木の解釈
重み付きラプラシアンの行列式は各全域木の辺の重みの積の総和に等しい。

よくあるミス

ミス原因正しい書き方
行/列の削除間違い余因子は同じ行列を削除同じインデックスの行と列を削除
ピボットが0部分ピボット探索が必要0でない行をスワップ
符号のミススワップで符号が変わるスワップごとに result *= -1

次のステップ

  • 発展: 有向グラフの全域樹形の数（有向版）
  • 応用: 辺の制約付き全域木の数

自己評価

自分の回答

気づき・メモ