Day 021-Q3 — マトロイド交差（Matroid Intersection）

問題

$N$ 個の要素からなる集合 $U = \{0, 1, \ldots, N-1\}$ がある。2つのマトロイド $M_1, M_2$ が与えられ、それぞれ独立集合族を持つ。

$M_1$: グラフ的マトロイド（Graphic Matroid）。$N$ 要素は辺に対応し、グラフ $G$ の辺集合 $E$ から森（閉路を含まない部分グラフ）を選ぶ。

$M_2$: 分割マトロイド（Partition Matroid）。$N$ 要素は $K$ グループ $G_1, G_2, \ldots, G_K$ に分割されており、各グループ $G_i$ から高々 $k_i$ 個選べる。

両マトロイドの独立集合の共通集合（Matroid Intersection）の最大サイズを求めよ。

入力形式

V E
u_1 v_1
u_2 v_2
...
u_E v_E
K
g_1 k_1
g_2 k_2
...
g_E k_E

制約

入出力例

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

3

ヒント (段階的開示)

# 交換グラフの辺：
# e ∈ I → f ∉ I: I - e + f ∈ M1 のとき e→f
# f ∉ I → e ∈ I: I - e + f ∈ M2 のとき f→e
# BFS で X1 の要素から X2 の要素への最短路を見つけ、
# その路上で I の要素とそれ以外を交互にswapする

模範解答 (Python)

📋 コピーimport sys
from collections import deque

def solve():
    data = sys.stdin.read().split()
    pos = 0

    V = int(data[pos]); pos += 1
    E = int(data[pos]); pos += 1

    edges = []
    for _ in range(E):
        u = int(data[pos]); pos += 1
        v = int(data[pos]); pos += 1
        edges.append((u, v))

    K = int(data[pos]); pos += 1

    group = [0] * E
    k_limit = {}
    for i in range(E):
        g = int(data[pos]); pos += 1
        ki = int(data[pos]); pos += 1
        group[i] = g
        k_limit[g] = ki

    def make_uf(n):
        return list(range(n))

    def find(uf, x):
        while uf[x] != x:
            uf[x] = uf[uf[x]]
            x = uf[x]
        return x

    def union(uf, x, y):
        x, y = find(uf, x), find(uf, y)
        if x == y:
            return False
        uf[x] = y
        return True

    def is_independent_M1(S):
        uf = make_uf(V)
        for e in S:
            u, v = edges[e]
            if not union(uf, u, v):
                return False
        return True

    def can_add_M1(S_set, e):
        uf = make_uf(V)
        for f in S_set:
            union(uf, edges[f][0], edges[f][1])
        u, v = edges[e]
        return find(uf, u) != find(uf, v)

    def can_exchange_M1(S_set, e, f):
        new_S = (S_set - {e}) | {f}
        return is_independent_M1(new_S)

    def can_add_M2(S_set, e):
        g = group[e]
        cnt = sum(1 for f in S_set if group[f] == g)
        return cnt < k_limit[g]

    def can_exchange_M2(S_set, e, f):
        new_S = (S_set - {e}) | {f}
        for g, lim in k_limit.items():
            if sum(1 for x in new_S if group[x] == g) > lim:
                return False
        return True

    I = set()

    while True:
        X1 = set(e for e in range(E) if e not in I and can_add_M1(I, e))
        X2 = set(e for e in range(E) if e not in I and can_add_M2(I, e))

        common = X1 & X2
        if common:
            I.add(next(iter(common)))
            continue

        dist = {e: -1 for e in range(E)}
        prev = {}
        queue = deque()

        for s in X1:
            dist[s] = 0
            queue.append(s)

        found = None
        while queue and found is None:
            cur = queue.popleft()
            if cur not in I:
                for e in list(I):
                    if can_exchange_M2(I, e, cur) and dist[e] == -1:
                        dist[e] = dist[cur] + 1
                        prev[e] = cur
                        queue.append(e)
            else:
                for f in range(E):
                    if f not in I and dist[f] == -1 and can_exchange_M1(I, cur, f):
                        dist[f] = dist[cur] + 1
                        prev[f] = cur
                        if f in X2:
                            found = f
                            break
                        queue.append(f)

        if found is None:
            break

        path = []
        node = found
        while node in prev:
            path.append(node)
            node = prev[node]
        path.append(node)

        for node in path:
            if node in I:
                I.remove(node)
            else:
                I.add(node)

    print(len(I))

solve()

Step-by-Step 解説

よくあるミス

次のステップ

• 発展問題: 重み付きマトロイド交差（最大重みの共通独立集合）
• 応用: 有向全域木（Directed Spanning Tree / Matroid Union）

自己評価

自分の回答

気づき・メモ