問題
$N$個のプロジェクトがあり、プロジェクト$i$を実行すると利益$w_i$（正または負）が得られる。$M$個の依存関係$(a_i,b_i)$が与えられ、それぞれ「$a_i$を選ぶなら$b_i$も必ず選ぶ」ことを意味する。
依存関係をすべて満たす部分集合$S\subseteq\{1,\dots,N\}$（空集合可）の中で、利益の総和$\sum_{i\in S}w_i$を最大化せよ。
入力形式
N M
w_1 w_2 ... w_N
a_1 b_1
...
a_M b_M制約
$1 \le N \le 300$
$0 \le M \le 3\times10^4$
$-10^9 \le w_i \le 10^9$
$1 \le a_i,b_i \le N,\ a_i \ne b_i$
入出力例
入力例1
3 2
10 -5 -3
1 2
1 3出力例1
2説明: プロジェクト1を選ぶと2,3も選ばねばならず利益 $10-5-3=2$。選ばなければ利益0。よって最大は2。
概念図
ヒント（段階的開示）
ヒント1（方向性）
「$a$を選ぶなら$b$も選ぶ」という依存関係を持つ最大化問題は、最小カットに帰着できる古典パターン（プロジェクト選択問題／最大重みクロージャ問題）である。
ヒント2（アプローチ）
超頂点$S,T$を用意し、$w_i>0$なら$S\to i$に容量$w_i$、$w_i<0$なら$i\to T$に容量$-w_i$の辺を張る。依存関係$(a,b)$には$a\to b$に容量$\infty$の辺を張る。最小カットを$C$とすると答えは$\left(\sum_{w_i>0}w_i\right)-C$。
ヒント3（誘導）
最小カットで$S$側に残る頂点集合が選択すべきプロジェクト。$\infty$辺がカットされないことがちょうど依存関係の充足を保証する。
# S=0, T=N+1
# w[i] > 0: add_edge(S, i, w[i])
# w[i] < 0: add_edge(i, T, -w[i])
# 依存 (a, b): add_edge(a, b, INF)
# answer = sum(w[i] for w[i] > 0) - 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 e in self.graph[u]:
v, cap, _ = e
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[u] < self.level[v]:
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 main():
data = sys.stdin.buffer.read().split()
idx = 0
N = int(data[idx]); idx += 1
M = int(data[idx]); idx += 1
w = [int(data[idx + i]) for i in range(N)]
idx += N
S = 0
T = N + 1
mf = MaxFlow(N + 2)
INF = float('inf')
total_positive = 0
for i in range(N):
v = i + 1
if w[i] > 0:
mf.add_edge(S, v, w[i])
total_positive += w[i]
elif w[i] < 0:
mf.add_edge(v, T, -w[i])
for _ in range(M):
a = int(data[idx]); idx += 1
b = int(data[idx]); idx += 1
mf.add_edge(a, b, INF)
cut = mf.max_flow(S, T)
print(total_positive - cut)
main()Step-by-Step 解説
1問題をカット問題に翻訳する
「$S$側=選ぶ」「$T$側=選ばない」と決め、正利益の機会損失、負利益のコストをそれぞれ辺の容量として表現する。
「$S$側=選ぶ」「$T$側=選ばない」と決め、正利益の機会損失、負利益のコストをそれぞれ辺の容量として表現する。
2正負での辺の張り方
$w_i>0$は$S\to i$に容量$w_i$（選ばないと損失）。$w_i<0$は$i\to T$に容量$-w_i$（選ぶとコスト）。
$w_i>0$は$S\to i$に容量$w_i$（選ばないと損失）。$w_i<0$は$i\to T$に容量$-w_i$（選ぶとコスト）。
3依存関係を無限容量辺で表現
$a\to b$に$\infty$の辺を張れば、$a$が$S$側かつ$b$が$T$側になるカットのコストが無限大になり選ばれない。
$a\to b$に$\infty$の辺を張れば、$a$が$S$側かつ$b$が$T$側になるカットのコストが無限大になり選ばれない。
4最小カット=最大流
最大流最小カット定理よりDinic法で$O(V^2E)$で計算できる。$N\le300,M\le3\times10^4$なら十分高速。
最大流最小カット定理よりDinic法で$O(V^2E)$で計算できる。$N\le300,M\le3\times10^4$なら十分高速。
5答えの復元
正利益の総和からカットを引いたものが最大利益。$S$から到達可能な頂点が実際の選択集合になる。
正利益の総和からカットを引いたものが最大利益。$S$から到達可能な頂点が実際の選択集合になる。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 依存関係の辺の向きを逆にする | 「$a$なら$b$」を$b\to a$と誤解 | $a\to b$に$\infty$容量。逆向きだと制約が守られない |
| $w_i=0$の扱いを誤解 | 辺なしで放置すればよいと考え頂点自体を削ってしまう | 辺は不要だが依存関係の中継点として頂点は必要 |
| total_positiveの計算漏れ | 正利益合計を答えの基準に使い忘れる | 答え=正利益合計-最小カットを必ず両方計算する |
| ∞容量をfloat('inf')にしてエラー | フロー計算でinf同士の演算が発生し得る | 十分大きい有限値(例:10^18)を使うか演算を避ける実装にする |
| Dinic法のitをBFS毎にリセットし忘れる | 前回のイテレータ位置を使い回す | 各BFS成功後に必ずit=[0]*nで初期化する |
次のステップ
- 発展: 「少なくとも1つを選べば良い」OR条件を含む場合、単純な最大重みクロージャでは表現できない。補助頂点を追加した拡張モデルを設計せよ。
- 発展2: $N$が大きい($10^5$規模)場合、ISAPやPush-Relabel法との計算量比較を実測せよ。
- 次回予告: 次回のテーマは今後のセッションで選定