Day 055-Q5 | Randomized Matroid Intersection（乱択マトロイド交差）

問題

$N$ 要素の全体集合 $E = \{1, \ldots, N\}$ に2つのマトロイドが定義されている:

$M_1$: グラフマトロイド — $V$ 頂点 $N$ 辺の無向グラフの辺集合上の森マトロイド
$M_2$: 分割マトロイド — $E$ が $k$ グループに分割され、各グループから高々 $c_i$ 本選べる

$M_1 \cap M_2$ の最大重み独立集合を求めよ（各辺に重みあり）。

制約

パラメータ	範囲
$V_{num}$	$2 \le V_{num} \le 500$
$N$	$1 \le N \le 2000$
$k$	$1 \le k \le N$
$w_i$	$1 \le w_i \le 10^9$

入出力例

入力例 1

出力例 1

辺 {1,3,5}（辺ID=1:w=10, ID=3:w=8, ID=5:w=7）でグラフは森 ✓。グループ1から2本以内 (ID 1,2,5→3本はNG)。最大重みは辺{1(w=10),3(w=8),5(w=7)}=25だがグループ制約で違反。最適は辺{1,3}=18か{1,5}=17か{3,5}=15... 別の組み合わせで 23。

概念図: 交換グラフ $D_I$ と増加路

ヒント（段階的開示）

ヒント1: 方向性

Lawler の重み付きマトロイド交差アルゴリズム。現在の独立集合 $I$ に対して、交換グラフ $D_I$ を構築し、$M_1$ で直接追加できる要素（$X_1$）から $M_2$ で直接追加できる要素（$X_2$）への最大重み増加路を BFS で探索。重みが改善する間繰り返す。

ヒント2: アプローチ

交換グラフ $D_I$ の辺:

$y \notin I$: $y_1 \in I$ に対し $(I \setminus \{y_1\}) \cup \{y\} \in M_1$ なら $y_1 \to y$ の $M_1$-swap 辺
$y \notin I$: $y_1 \in I$ に対し $(I \setminus \{y_1\}) \cup \{y\} \in M_2$ なら $y_1 \to y$ の $M_2$-swap 辺
$X_1 = \{y \notin I : I \cup \{y\} \in M_1\}$（直接追加可能）
$X_2 = \{y \notin I : I \cup \{y\} \in M_2\}$（直接追加可能）

BFS で $X_1$ から $X_2$ への最大重み最短路を探す。

ヒント3: コード骨格

# グラフマトロイド M1: Union-Find で閉路判定
def indep1(S):
    uf = UF(V_num)
    for e in S:
        u, v, _ = edges[e]
        if not uf.union(u, v): return False
    return True

# 分割マトロイド M2: グループ上限チェック
def indep2(S):
    cnt = [0] * (k+1)
    for e in S:
        cnt[group[e]] += 1
        if cnt[group[e]] > cap[group[e]]: return False
    return True

# 最大重み増加路 BFS
dist = {y: -INF for y in E_minus_I}
for y in X1: dist[y] = w[y]
# BFS: y → (M1-swap: y1∈I) → (M2-swap: z∉I)
for y1 in I:
    if (I\{y1}∪{y}) ∈ M1:  # M1-swap
        for z in E_minus_I:
            if (I\{y1}∪{z}) ∈ M2:  # M2-swap
                nd = dist[y] - w[y1] + w[z]
                if nd > dist[z]: dist[z] = nd; ...

模範解答 (Python)

import sys
from collections import deque
input = sys.stdin.readline

class UF:
    def __init__(self, n):
        self.p = list(range(n)); self.r = [0]*n
    def find(self, x):
        while self.p[x] != x: x = self.p[x] = self.p[self.p[x]]
        return x
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return False
        if self.r[x] < self.r[y]: x, y = y, x
        self.p[y] = x
        if self.r[x] == self.r[y]: self.r[x] += 1
        return True

def solve():
    line = list(map(int, input().split()))
    V_num, N, k = line
    edges = []
    for _ in range(N):
        u, v, w = map(int, input().split())
        edges.append((u-1, v-1, w))
    group = list(map(int, input().split()))
    cap = [0] + list(map(int, input().split()))

    w_arr = [e[2] for e in edges]

    def indep1(S):
        uf = UF(V_num)
        for e in S:
            u, v, _ = edges[e]
            if not uf.union(u, v): return False
        return True

    def indep2(S):
        cnt = [0]*(k+1)
        for e in S:
            g = group[e]; cnt[g] += 1
            if cnt[g] > cap[g]: return False
        return True

    def can_swap1(I, e_out, e_in):
        return indep1([x for x in I if x != e_out] + [e_in])

    def can_swap2(I, e_out, e_in):
        return indep2([x for x in I if x != e_out] + [e_in])

    I = set()
    total_w = 0

    for _ in range(N):
        I_list = list(I)
        OUT = [e for e in range(N) if e not in I]

        X1 = {y for y in OUT if indep1(I_list + [y])}
        X2 = {y for y in OUT if indep2(I_list + [y])}
        if not X1 or not X2: break

        INF = float('inf')
        dist = {y: -INF for y in OUT}
        prev = {y: None for y in OUT}
        visited = set()

        for y in X1:
            dist[y] = w_arr[y]
            visited.add(y)

        queue = deque(X1)
        while queue:
            y = queue.popleft()
            for y1 in I_list:
                if can_swap1(I, y1, y):
                    for z in OUT:
                        if z == y: continue
                        if can_swap2(I, y1, z) and z not in visited:
                            nd = dist[y] - w_arr[y1] + w_arr[z]
                            if nd > dist.get(z, -INF):
                                dist[z] = nd; prev[z] = (y, y1)
                                visited.add(z); queue.append(z)

        best_goal, best_val = None, 0
        for y in X2:
            if y in visited and dist[y] > best_val:
                best_val = dist[y]; best_goal = y

        if best_goal is None: break

        path_out = set(); path_in = set()
        cur = best_goal; path_in.add(cur)
        while prev[cur] is not None:
            y, y1 = prev[cur]; path_out.add(y1); cur = y; path_in.add(cur)
        I = (I | path_in) - path_out
        total_w += best_val

    print(total_w)

solve()

Step-by-Step 解説

1マトロイドの独立性オラクル実装
$M_1$（グラフマトロイド）: Union-Find で閉路検出。$M_2$（分割マトロイド）: グループごとの計数。両方とも $O(N)$ per oracle。

2交換グラフ $D_I$ の定義
$I$ が現在の独立集合。$y \notin I$ のとき: $M_1$ 的に $(I \setminus \{y_1\}) \cup \{y\} \in M_1$ なら「$M_1$-swap 辺」、$M_2$ 的に同様なら「$M_2$-swap 辺」。

3最大重み増加路の探索
$X_1$（$M_1$ で直接追加可能）から始め、$X_2$（$M_2$ で直接追加可能）への最大重み路を BFS で探索。重みはパスで追加した要素の重み - 削除した要素の重みの合計。

4増加路で解を更新・繰り返し
増加路 $P$ に対し $I \leftarrow I \triangle P$（対称差）。重み改善幅が正の間繰り返す。最悪 $r$ 回（$r$ = 最大独立集合のランク）。

計算量

反復回数: $O(r)$（$r$ = 最大独立集合サイズ）
各反復での BFS: $O(N^2 \cdot T_{oracle})$（$N^2$ 対の swap 確認 × oracle $O(N)$）
全体: $O(r \cdot N^3)$ — 今回の制約 ($N \le 2000$) で実用的
Oracle の効率化（インクリメンタル更新）で改善可能

よくあるミス

ミス	原因	正しい書き方
増加路の復元ミス	prev の定義が不明瞭	`prev[z] = (y, y1)` で記録（y=直前, y1=削除した I の要素）
重み改善幅の判定ミス	0以下の増加路を取る	`best_val > 0` の時のみ更新
交換可能性の oracle 実装ミス	削除要素を除いた集合で判定	`[x for x in I if x != e_out] + [e_in]`
ループ上限がない	無限ループのリスク	`for _ in range(N):` で最大 N 回に制限

次のステップ

発展問題: 3つのマトロイドの交差（NP困難だが近似アルゴリズムが存在）
関連: マトロイドの和（Matroid Union / Matroid Partitioning）
応用: グラフ上の $k$-色スパニングツリー（$k$ 個の森マトロイドの和）

自己評価

完全理解おおむね理解要復習