Day 097-Q5 — 次数制約部分グラフ（b-マッチング・最大流帰着）

2026-07-20 赤色 Master / Phase 8+ ★★★★★★★★★ b-マッチング

問題

左側頂点 $1,\dots,N$、右側頂点 $1,\dots,M$ を持つ二部グラフが与えられる。左頂点 $i$ には上限次数 $b_i$、右頂点 $j$ には上限次数 $c_j$ が定められている。与えられた $E$ 本の辺のうち何本かを選び、各頂点の次数上限を守ったまま選べる辺の本数の最大値を求めよ。

入力形式

N M E
b_1 ... b_N
c_1 ... c_M
u_1 v_1
:
u_E v_E

制約

$1 \le N,M \le 300$
$1 \le E \le 3\times10^4$
$0 \le b_i \le M,\ 0 \le c_j \le N$

入出力例

入力例1

2 2 3
2 1
1 2
1 1
1 2
2 2

出力例1

3

左頂点1(上限2)が右頂点1・2の両方に、左頂点2(上限1)が右頂点2に辺を持つ、という3本すべてを選んでも制約を満たす。

概念図

b-マッチングの最大流ネットワーク S L1 L2 R1 R2 T b1 b2 cap 1 c1 c2 最大流量 = 次数制約を守って選べる辺の最大本数

ヒント（段階的開示）

ヒント1: 方向性
通常の二部マッチング（各頂点が高々1本）は最大流の特殊ケースだった。各頂点の上限が1より大きい場合も、頂点の容量として最大流のネットワークに組み込めないかを考えよ。
ヒント2: アプローチ
ソース $S$ から各左頂点 $i$ へ容量 $b_i$ の辺、各右頂点 $j$ からシンク $T$ へ容量 $c_j$ の辺を張り、与えられた各辺 $(u,v)$ には容量1の辺を張る。この最大流ネットワークの最大流量が答え。
ヒント3: 誘導（コード骨格） 
S, T = N + M, N + M + 1
mf = MaxFlow(N + M + 2)
for i in range(N):
    mf.add_edge(S, i, b[i])
for j in range(M):
    mf.add_edge(N + j, T, c[j])
for u, v in edges:
    mf.add_edge(u, N + v, 1)
print(mf.max_flow(S, T))

模範解答 (Python)

import sys
from collections import deque


class MaxFlow:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]

    def add_edge(self, u, v, cap):
        self.graph[u].append([v, cap, len(self.graph[v])])
        self.graph[v].append([u, 0, len(self.graph[u]) - 1])

    def bfs(self, s, t):
        self.level = [-1] * self.n
        self.level[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v, cap, _ in self.graph[u]:
                if cap > 0 and self.level[v] < 0:
                    self.level[v] = self.level[u] + 1
                    q.append(v)
        return self.level[t] >= 0

    def dfs(self, u, t, f):
        if u == t:
            return f
        while self.it[u] < len(self.graph[u]):
            e = self.graph[u][self.it[u]]
            v, cap, rev = e
            if cap > 0 and self.level[v] == self.level[u] + 1:
                d = self.dfs(v, t, min(f, cap))
                if d > 0:
                    e[1] -= d
                    self.graph[v][rev][1] += d
                    return d
            self.it[u] += 1
        return 0

    def max_flow(self, s, t):
        flow = 0
        while self.bfs(s, t):
            self.it = [0] * self.n
            while True:
                f = self.dfs(s, t, float('inf'))
                if f == 0:
                    break
                flow += f
        return flow


def solve():
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1
    e_cnt = int(data[idx]); idx += 1
    b = [int(data[idx + i]) for i in range(n)]; idx += n
    c = [int(data[idx + i]) for i in range(m)]; idx += m
    edges = []
    for _ in range(e_cnt):
        u = int(data[idx]) - 1; idx += 1
        v = int(data[idx]) - 1; idx += 1
        edges.append((u, v))

    S, T = n + m, n + m + 1
    mf = MaxFlow(n + m + 2)
    for i in range(n):
        mf.add_edge(S, i, b[i])
    for j in range(m):
        mf.add_edge(n + j, T, c[j])
    for u, v in edges:
        mf.add_edge(u, n + v, 1)

    print(mf.max_flow(S, T))


solve()
計算量: Dinic法は一般に $O(V^2E)$ だが、単位容量に近い二部グラフ構造では $O(E\sqrt{V})$ 程度で動作することが多い。

Step-by-Step 解説

1ネットワークの構築
$S\to$左頂点$i$に容量$b_i$、右頂点$j\to T$に容量$c_j$、各入力辺に容量1を張る。
2各辺の容量1が意味すること
入力辺は「選ぶか選ばないか」の0/1変数なので容量1とする。
3Dinic法による最大流計算
BFSでレベルグラフを構築し、DFSでブロッキングフローを繰り返し求める。
4最大流量が答え
フロー保存則により、選べる辺の本数の最大値と一致する。

よくあるミス

ミス原因正しい書き方
入力辺の容量を無限大にしてしまう通常の最大流と混同与えられた辺は高々1回しか選べないので容量1にする
左右の上限を辺側の制約と勘違い頂点容量とS/T接続辺の対応を理解していない$S\to$左頂点、右頂点$\to T$の容量として頂点上限を表現する
逆辺の初期容量を0にし忘れる残余グラフの概念を理解していないadd_edgeで必ず逆辺を容量0で同時に追加する
右頂点のインデックスにNを足し忘れる頂点番号のオフセット管理ミス右頂点jは必ずn+jとして扱う

次のステップ

  • 発展: 各辺に重みがある場合の最大重みb-マッチング（最小費用流に帰着）
  • 発展: 下限も課された次数制約部分グラフ（下限付きフローの技法が必要）
  • 次回予告: 輪郭線DP（Broken Profile DP）のバリエーション、あるいは新規テーマ

自己評価

自分の回答

気づき・メモ