Day 078-Q3 — 重み付きマトロイド交差（グラフ×分割マトロイド）

2026-07-02 赤色 Master / Phase 8+ ★★★★★★★★★ マトロイド交差・増加路・Bellman-Ford

問題

グラフ $(V, E)$ と色集合 $C$ が与えられる。各辺 $e_i$ は色 $c_i$ と重み $w_i > 0$ を持つ。次の条件を両方満たすスパニングフォレストの中で、重み最大のものを求めよ。

  1. 選んだ辺がスパニングフォレストを形成する（グラフマトロイド）
  2. 同じ色の辺を 2 本以上選ばない（分割マトロイド）

制約

パラメータ範囲備考
$N$$2 \le N \le 200$頂点数
$M$$1 \le M \le 500$辺数
$c_i$$1 \le c_i \le M$色番号
$w_i$$1 \le w_i \le 10^4$重み

入出力例

入力例1

4 5
1 2 1 10
1 3 1 8
2 3 2 6
2 4 3 7
3 4 2 5

出力例1

23

辺 (1,2,色1,w=10)+(2,4,色3,w=7)+(2,3,色2,w=6)=23 が最大。色1・色2・色3 各1本、スパニングフォレスト形成。

概念図: 補助有向グラフ $D_I$

重み付きマトロイド交差の補助有向グラフ I = 現在の独立集合 E\I = I に含まれない要素 S=仮想始点, T=仮想終点 M1（グラフマトロイド）の辺 x ∉ I → y ∈ I: (I - y + x) がフォレスト （辺 x を追加、辺 y を除去するとフォレスト） 辺の重み: w[x] - w[y] S → x (x を直接 I に追加できる場合) M2（分割マトロイド）の辺 y ∈ I → x ∉ I: (I - y + x) の色制約 OK （辺 y を除去、辺 x を追加で色上限 OK） 辺の重み: w[x] - w[y] x → T (x を I に追加して M2 独立) 最大重み増加路 S → x1 → y1 → x2 → T S: 仮想始点（I に直接追加可能な x から出発） x ∉ I: I に追加する要素（+w[x]） y ∈ I: I から除去する要素（-w[y]） 路の重みの和 > 0 なら I を更新して重みが増加

ヒント

ヒント1（方向性）

「スパニングフォレスト ∩ 色上限1」はグラフマトロイドと分割マトロイドの交差問題。重み付きマトロイド交差は補助有向グラフ上の最大重み増加路を繰り返すことで解ける。

ヒント2（アプローチ）

補助有向グラフ $D_I$ を構築し、$S \to T$ への最大重み路 $P$ を Bellman-Ford で求める。$P$ に沿って $I = I \triangle P$ で更新。重みが増加しなくなったら終了。

ヒント3（ほぼ答え） 
def add_edge(u, v):
    # M1: (I - v + u) がフォレスト？
    # M2: (I - v + u) の色制約 OK？
    # 補助グラフに辺を追加
    ...

# Bellman-Ford で最大重み路
d = [-INF] * (M+2)
d[S] = 0
for _ in range(M+2):
    for u,v,w in graph_edges:
        if d[u] != -INF and d[u]+w > d[v]:
            d[v] = d[u]+w; par[v] = u

模範解答

import sys
from collections import defaultdict

def solve():
    data = sys.stdin.read().split()
    idx = 0
    N = int(data[idx]); idx+=1
    M = int(data[idx]); idx+=1
    edges = []
    for _ in range(M):
        u=int(data[idx])-1;idx+=1; v=int(data[idx])-1;idx+=1
        c=int(data[idx])-1;idx+=1; w=int(data[idx]);idx+=1
        edges.append((u,v,c,w))

    class DSU:
        def __init__(self,n): self.p=list(range(n)); self.r=[0]*n
        def find(self,x):
            while self.p[x]!=x: self.p[x]=self.p[self.p[x]]; x=self.p[x]
            return x
        def same(self,x,y): return self.find(x)==self.find(y)
        def union(self,x,y):
            x,y=self.find(x),self.find(y)
            if x==y: return False
            if self.r[x]d[v]:
                    d[v]=d[u]+w; par[v]=u; upd=True
            if not upd: break

        if d[T]<=0: break

        cur=T; path=[]
        while cur!=S: path.append(cur); cur=par[cur]
        path.reverse()
        for node in path:
            if node==T: continue
            if node in I: I.remove(node); color_cnt[edges[node][2]]-=1
            else: I.add(node); color_cnt[edges[node][2]]+=1

    print(sum(edges[e][3] for e in I))

solve()

Step-by-Step 解説

Step 1: マトロイド交差とは

2つのマトロイドの共通独立集合を求める問題。多項式時間で解ける（3つ以上はNP困難）。

Step 2: 補助有向グラフ $D_I$

辺条件重み
$S \to x$$x \notin I$、$\mathcal{M}_1$ と $\mathcal{M}_2$ どちらも独立$+w[x]$
$x \to y$$x \notin I, y \in I$、$\mathcal{M}_1$ で $(I-y+x) \in \mathcal{I}_1$$w[x]-w[y]$
$y \to x$$y \in I, x \notin I$、$\mathcal{M}_2$ で $(I-y+x) \in \mathcal{I}_2$$w[x]-w[y]$
$x \to T$$x \notin I$、$\mathcal{M}_2$ で $(I+x) \in \mathcal{I}_2$$0$

Step 3: 最大重み増加路

$S$ から $T$ への最大重み路 $P$ を Bellman-Ford で求め、$I \triangle P$ で更新する。$d[T] \le 0$ なら終了。

Step 4: 計算量

1回の増加路探索は $O(M^2 \cdot (N + M))$（DSU での独立判定を含む）。最大 $M$ 回繰り返すので全体 $O(M^3 (N+M))$。$N, M \le 500$ では十分。

よくあるミス

ミス原因正しい書き方
マトロイドの方向を混同する$D_I$ の辺の向きを誤る$\mathcal{M}_1$ 用と $\mathcal{M}_2$ 用の辺を区別する
増加路の重みが 0 以下でも更新する重みが減少するd[T] > 0 のときのみ更新
color_cnt の管理ミス分割マトロイドの判定が壊れるI 更新と同時に color_cnt を維持

次のステップ

発展問題: $k$-マトロイド交差（近似アルゴリズム・局所探索法）

自己評価