問題
$N$ 個のプロジェクトと $M$ 個のリソースがある。プロジェクト $i$ を選択すると利益 $p_i$（正値）が得られるが、リソース $j$ の購入コストは $c_j$（正値）。また依存関係があり、「プロジェクト $i$ を選ぶならプロジェクト $k$ も選ばなければならない」という制約がある。選択するプロジェクトの集合 $S$ に対して最大利益を求めよ。
制約
$1 \le N, M \le 500$
$1 \le E \le 2000$（依存辺数）
$1 \le p_i, c_j \le 10^9$
利益 = $\sum p_i - \sum$ (必要リソースコスト)
時間制限: 2秒
入出力例
入力例 1
3 2 2
10 20 5
8 12
1 1
2 2
2 3出力例 1
15
プロジェクト2（p=20）を選ぶ → リソース2（c=12）が必要 → 利益 20-12=8
プロジェクト1+2（p=10+20=30）→ リソース1+2（c=8+12=20）→ 利益 10
プロジェクト1+2+3（p=35）→ リソース1+2（c=20）→ 利益 15（最大）
概念図: 最大重みクロージャのネットワーク構築
ヒント（段階的開示）
ヒント1: 方向性
「プロジェクト選択問題（Project Selection Problem）」は最大重みクロージャ（Maximum Weight Closure）に帰着でき、さらに最小カット（= 最大流）に帰着できます。
ヒント2: ネットワークの構築
- ソース $s$ から各プロジェクト $i$ へ容量 $p_i$ の辺
- 各リソース $j$ からシンク $t$ へ容量 $c_j$ の辺
- プロジェクト $i$ がリソース $j$ を必要とする → $i \to j$ へ容量 $\infty$ の辺
- プロジェクト間依存（$i$ には $k$ が必要）→ $i \to k$ へ容量 $\infty$ の辺
- 最大利益 = 正利益の総和 − 最小カット
ヒント3: 最小カットの解釈
カットに含まれる辺は「切り離す辺」を意味する。$s$ 側カットに含まれる辺の容量 = 諦めた利益（プロジェクトを選ばない）+ 購入したリソースのコスト。これを最小化することで最大利益を得る。
total_profit = sum(profits)
min_cut = dinic.max_flow(S, T)
answer = total_profit - min_cut模範解答 (Python)
import sys
from collections import deque
def solve():
data = sys.stdin.read().split()
idx = 0
N, M, E = int(data[idx]), int(data[idx+1]), int(data[idx+2]); idx += 3
profits = [int(data[idx+i]) for i in range(N)]; idx += N
costs = [int(data[idx+i]) for i in range(M)]; idx += M
S = 0
T = N + M + 1
num_nodes = T + 1
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:
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, iter_):
if v == t:
return f
while iter_[v] < len(self.graph[v]):
e = self.graph[v][iter_[v]]
to, cap, rev = e
if cap > 0 and self.level[v] < self.level[to]:
d = self.dfs(to, t, min(f, cap), iter_)
if d > 0:
e[1] -= d
self.graph[to][rev][1] += d
return d
iter_[v] += 1
return 0
def max_flow(self, s, t):
flow = 0
INF = float('inf')
while self.bfs(s, t):
iter_ = [0] * self.n
while True:
f = self.dfs(s, t, INF, iter_)
if f == 0:
break
flow += f
return flow
mf = MaxFlow(num_nodes)
INF = 10**18
total_profit = 0
for i in range(N):
mf.add_edge(S, i+1, profits[i])
total_profit += profits[i]
for j in range(M):
mf.add_edge(N+j+1, T, costs[j])
for _ in range(E):
a, b = int(data[idx])-1, int(data[idx+1])-1; idx += 2
mf.add_edge(a+1, b+1, INF)
min_cut = mf.max_flow(S, T)
print(total_profit - min_cut)
solve()
Step-by-Step 解説
1最大重みクロージャへの帰着
「クロージャ」とは、選んだ頂点集合から出る辺の行き先も必ず選ばれている集合。プロジェクト選択問題はこの構造を持つ。
「クロージャ」とは、選んだ頂点集合から出る辺の行き先も必ず選ばれている集合。プロジェクト選択問題はこの構造を持つ。
2ネットワーク構築の設計
正利益をソース側（s→プロジェクト）、コストをシンク側（リソース→t）に配置。依存関係は容量 ∞ の辺で表現する。
正利益をソース側（s→プロジェクト）、コストをシンク側（リソース→t）に配置。依存関係は容量 ∞ の辺で表現する。
3最小カットの解釈
s 側のカット辺 = 諦めた利益（プロジェクトの利益を失う）。t 側のカット辺 = 購入するリソースのコスト。最小カットはこれらの和を最小化する。
s 側のカット辺 = 諦めた利益（プロジェクトの利益を失う）。t 側のカット辺 = 購入するリソースのコスト。最小カットはこれらの和を最小化する。
4Dinic 法で最大流を計算
Dinic 法の計算量は $O(V^2 E)$。本問では N, M, E が小さいので十分高速。
Dinic 法の計算量は $O(V^2 E)$。本問では N, M, E が小さいので十分高速。
計算量
ノード数: $O(N + M)$
辺数: $O(N + M + E)$
Dinic 最大流: $O(V^2 E) = O((N+M)^2 (N+M+E))$
全体: 本問の制約で十分高速
辺数: $O(N + M + E)$
Dinic 最大流: $O(V^2 E) = O((N+M)^2 (N+M+E))$
全体: 本問の制約で十分高速
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 依存辺の容量を有限にする | カットに含まれてしまう | 容量 INF（十分大きい数）に設定 |
| 正利益の総和を計算しない | 答えが求まらない | total_profit - min_cut が答え |
| 逆辺の容量管理ミス | 最大流の実装バグ | add_edge で必ず逆辺（容量0）も追加 |
| コスト辺の向きを逆にする | カットの向きが逆 | リソース → T（シンク方向） |
次のステップ
- 発展問題: 最大密度部分グラフ（Goldberg アルゴリズム、二分探索 + 最大流）
- 関連: Day042 Q4（最大密度部分グラフ）の復習
- 応用: Project Selection Problem の多次元拡張、OR最適化