Day 070-Q5 | Parametric Max-Flow（パラメトリック最大流 + Project Selection + λ最適化）

問題

$N$ 個のプロジェクトと $M$ 個のリソースがある。プロジェクト $i$ を実行すると利益 $p_i$ が得られるが、リソース集合 $R_i$ を全て使用する必要がある。リソース $j$ 使用のコストは $c_j + \lambda$（$\lambda$ はパラメータ）。純利益（利益 - コスト）を最大化し、複数の $\lambda$ に対して答えを出力せよ。

制約

パラメータ	範囲
$N, M$	$1 \le N, M \le 50$
$p_i, c_j$	$1 \le p_i, c_j \le 10^6$
$Q$（クエリ数）	$1 \le Q \le 100$
$\lambda$	$-10^6 \le \lambda \le 10^6$（整数）

入出力例

入力例 1

出力例 1

8
-1

$\lambda=0$: コスト=[3,2,4,6]。プロジェクト1実行(+10, コスト3+2=5) → 純利益5。プロジェクト2実行(+8, コスト2+4=6) → 純利益2。プロジェクト1+2実行(+18, コスト3+2+4=9) → 純利益9... 最適を最大流で計算すると8。

概念図: Project Selection の最大流グラフ

ヒント（段階的開示）

ヒント1: 方向性

Project Selection Problem（最大重みクロージャ）は最大流で解く。ノード設計: source → プロジェクト（容量 $p_i$）、リソース → sink（容量 $c_j + \lambda$）、プロジェクト → 必要リソース（容量 $\infty$）。最大純利益 $= \sum p_i - \text{最大流}$。

ヒント2: アプローチ

$\lambda$ ごとにフローグラフを再構築して Dinic 法を実行
負コスト（$c_j + \lambda < 0$）のリソースは「必ず使う」が最適 → 0 に固定して別途補正
最大流値が最小カット値 = 最大純利益の損失

ヒント3: コード骨格

s = 0; t = N + M + 1
mf = MaxFlow(N + M + 2)
total_profit = 0
for i in range(N):
    mf.add_edge(s, i+1, profits[i])
    total_profit += profits[i]
    for j in requires[i]:
        mf.add_edge(i+1, N+1+j, 10**18)
for j in range(M):
    c = max(0, costs[j])
    mf.add_edge(N+1+j, t, c)
neg_sum = sum(min(0, c) for c in costs)
ans = total_profit - mf.max_flow(s, t) + neg_sum

模範解答 (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):
        fwd = [v, cap, None]; bwd = [u, 0, None]
        fwd[2] = bwd; bwd[2] = fwd
        self.graph[u].append(fwd); self.graph[v].append(bwd)

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

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

    def max_flow(self, s, t):
        flow = 0
        while self.bfs(s, t):
            self.iter = [0]*self.n
            while True:
                f = self.dfs(s, t, 10**18)
                if f == 0: break
                flow += f
        return flow

def solve_lambda(N, M, profits, base_costs, requires, lam):
    costs = [c + lam for c in base_costs]
    s = 0; t = N+M+1
    mf = MaxFlow(N+M+2)
    total_profit = 0
    for i in range(N):
        mf.add_edge(s, i+1, profits[i])
        total_profit += profits[i]
        for j in requires[i]:
            mf.add_edge(i+1, N+1+j, 10**18)
    neg_sum = 0
    for j in range(M):
        c = costs[j]
        if c < 0:
            neg_sum += c
            mf.add_edge(N+1+j, t, 0)
        else:
            mf.add_edge(N+1+j, t, c)
    return total_profit - mf.max_flow(s, t) + neg_sum

def solve():
    data = sys.stdin.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    Q = int(data[idx]); idx += 1
    profits = [int(data[idx+i]) for i in range(N)]; idx += N
    base_costs = [int(data[idx+i]) for i in range(M)]; idx += M
    requires = []
    for i in range(N):
        req = []
        while True:
            v = int(data[idx]); idx += 1
            if v == -1: break
            req.append(v-1)
        requires.append(req)
    lambdas = [int(data[idx+i]) for i in range(Q)]; idx += Q
    for lam in lambdas:
        print(solve_lambda(N, M, profits, base_costs, requires, lam))

solve()

Step-by-Step 解説

Step 1: Project Selection Problem

「プロジェクト実行 → 依存リソース必須使用」を最大流グラフで表現。最大純利益 $= \sum p_i - \text{最大流}$。

Step 2: Dinic 法の計算量

一般グラフで $O(V^2 E)$。今回 $N, M \le 50$ なのでノード数 $\le 102$、辺数 $\le 2650$。各 $\lambda$ に対して $O(V^2 E) \approx 10^7$ → $Q \le 100$ で $10^9$ 未満。

Step 3: 負コストリソースの補正

$c_j + \lambda < 0$ のとき、そのリソースを「必ず使う（コストが負なので無料で利益になる）」が最適。フローグラフでは容量 0 の辺にし、補正値を別途加算する。

Step 4: パラメトリック最大流の性質

$\lambda$ を変化させると最大流値は $\lambda$ の区分線形凸関数になる。最適 $\lambda$ は三分探索で求められる（今回は全 $\lambda$ 計算）。

Step 5: 最小カットの意味

カットされた辺	意味
$s \to P_i$（容量 $p_i$）	プロジェクト $i$ を実行しない
$R_j \to t$（容量 $c_j + \lambda$）	リソース $j$ を使用しない

よくあるミス

ミス	原因	正しい書き方
負コストリソースの扱いを忘れる	$c_j + \lambda < 0$ でグラフが不正	容量を `max(0, c)` にして補正
INF の設定が小さすぎる	フロー上限が不足	`10**18` を使用
双方向エッジの reverse ポインタミス	残余グラフが正しく管理されない	`fwd[2] = bwd; bwd[2] = fwd`
$\lambda$ ごとにグラフを再生成しない	前の計算結果が残る	各 $\lambda$ で `MaxFlow` オブジェクトを新規作成

次のステップ

発展問題: Aliens Trick (WQS 二分探索) との組み合わせ
最小費用流 (MCMF) による重み付きプロジェクト選択
$\lambda$ に関する凸性を利用した三分探索 $O(\log(\lambda_{\max}) \cdot V^2 E)$ 解法
マルチソース・マルチシンクへの拡張

Day 070-Q5 — Parametric Max-Flow（パラメトリック最大流 + Project Selection + λ最適化）

問題

制約