問題
$N$ 個のプロジェクトと $M$ 個の依存関係 (i,j)（i を選ぶなら j も選ぶ）がある。選ぶ集合がクロージャを満たすとき利益合計を最大化せよ。
制約
$1 \le N \le 500$
$0 \le M \le 5000$
$-10^6 \le w_i \le 10^6$
$i \ne j$
入出力例
入力例 1
4 3
5 -3 2 -2
1 2
1 3
3 4出力例 1
4ヒント (段階的開示)
ヒント1: 方向性
最大重みクロージャ問題 = 最小カット（最大流）への帰着。
ヒント2: アプローチ
正の重み: $S \to v$ 容量 $w_v$。負の重み: $v \to T$ 容量 $|w_v|$。依存辺 $(i,j)$: $i \to j$ 容量 $\infty$。最大利益 = 正の和 − 最大流。
ヒント3: Dinic
Dinic 法で $O(V^2 E)$、頂点数 $N+2$、辺数 $M+N$。
模範解答 (Python)
import sys
from collections import deque
input = sys.stdin.readline
class Dinic:
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:
v = q.popleft()
for to, cap, _ in self.graph[v]:
if cap > 0 and self.level[to] < 0:
self.level[to] = self.level[v] + 1
q.append(to)
return self.level[t] >= 0
def _dfs(self, v, t, f):
if v == t: return f
while self._iter[v] < len(self.graph[v]):
to, cap, rev = self.graph[v][self._iter[v]]
if cap > 0 and self.level[v] < self.level[to]:
d = self._dfs(to, t, min(f, cap))
if d > 0:
self.graph[v][self._iter[v]][1] -= d
self.graph[to][rev][1] += d
return d
self._iter[v] += 1
return 0
def max_flow(self, s, t):
flow = 0
INF = float('inf')
while self._bfs(s, t):
self._iter = [0] * self.n
while True:
f = self._dfs(s, t, INF)
if f == 0: break
flow += f
return flow
def solve():
N, M = map(int, input().split())
W = list(map(int, input().split()))
S, T = N, N + 1
dn = Dinic(N + 2)
INF = 10**18
pos_sum = 0
for i in range(N):
if W[i] > 0:
dn.add_edge(S, i, W[i])
pos_sum += W[i]
elif W[i] < 0:
dn.add_edge(i, T, -W[i])
for _ in range(M):
u, v = map(int, input().split())
dn.add_edge(u-1, v-1, INF)
print(pos_sum - dn.max_flow(S, T))
solve()Step-by-Step 解説
1クロージャの理解
$i$ を選ぶなら $j$ も選ぶ。閉集合制約。
$i$ を選ぶなら $j$ も選ぶ。閉集合制約。
2最大流への帰着
$S$-$T$ カットを「選ぶ/選ばない」境界として解釈。依存辺 $\infty$ で切断不能。
$S$-$T$ カットを「選ぶ/選ばない」境界として解釈。依存辺 $\infty$ で切断不能。
3Dinic 法
BFS でレベルグラフ、DFS でブロッキングフロー。
BFS でレベルグラフ、DFS でブロッキングフロー。
4選択頂点の特定
最大流後の BFS でソース側到達可能頂点が選ばれたプロジェクト。
最大流後の BFS でソース側到達可能頂点が選ばれたプロジェクト。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| INF が小さい | 依存辺が切れる | $\infty = 10^{18}$ |
| 辺方向の誤り | 逆向きに張る | 依存 $(i,j)$ は $i \to j$ |
| 符号誤り | 負の重みの方向 | add_edge(v, T, -W[v]) |
| $W=0$ を含める | pos_sum の集計 | if W[i] > 0: で限定 |
次のステップ
- QPBO / Generalized Project Selection