Day 046-Q4 | 最大重みクロージャ拡張（依存関係 + 排他条件 + Dinic）

問題

$N$ 個のプロジェクトがある。プロジェクト $i$ を実施すると利益 $p_i$（正または負）が得られる。各プロジェクトには依存関係があり、$M$ 本の有向辺 $(u, v)$ は「プロジェクト $u$ を選ぶなら $v$ も選ばなければならない」を意味する。

さらに $K$ 個の排他条件 $(a, b)$ があり、「$a$ と $b$ を同時に選ぶことはできない」。

選択するプロジェクトの集合を選んで、利益の合計を最大化せよ。

制約

$1 \le N \le 500$

$0 \le M \le 2000$

$0 \le K \le 1000$

$-10^6 \le p_i \le 10^6$

時間制限: 2秒

入出力例

入力例 1

出力例 1

概念図: 最大重みクロージャのフローネットワーク

ヒント（段階的開示）

ヒント1: 方向性

依存関係のみなら「最大重みクロージャ問題」として最大流（Dinic法）で解けます。排他条件は追加の容量制限辺と補助ノードで表現できます。

ヒント2: 基本の最大重みクロージャ

ソース $s$、シンク $t$ を追加
$p_i > 0$: $s \to i$（容量 $p_i$）
$p_i \le 0$: $i \to t$（容量 $|p_i|$）
依存辺 $(u, v)$: $u \to v$（容量 $\infty$）
最適値 = $\sum_{p_i > 0} p_i$ - 最大流

ヒント3: 排他条件の表現

排他条件 $(a, b)$ に補助ノード $c$ を追加:

$a \to c$（容量 $\infty$）
$b \to c$（容量 $\infty$）
$c \to t$（容量 = $a$ の正利益 + $b$ の正利益）

$a$ と $b$ を同時に選択すると $c$ を通る不可避なフローが発生し、カットとして計上される。

模範解答 (Python)

import sys
from collections import deque
input = sys.stdin.readline
INF = 10**18

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):
        if v == t: return f
        while self.iter[v] < len(self.graph[v]):
            e = self.graph[v][self.iter[v]]
            to, cap, rev = e
            if cap > 0 and self.level[v] < self.level[to]:
                d = self.dfs(to, t, min(f, cap))
                if d > 0:
                    e[1] -= d
                    self.graph[to][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, INF)
                if f == 0: break
                flow += f
        return flow


def main():
    N, M, K = map(int, input().split())
    p = list(map(int, input().split()))

    S = 0
    T = N + K + 1
    mf = MaxFlow(N + K + 2)

    pos_sum = 0
    for i in range(N):
        if p[i] > 0:
            mf.add_edge(S, i+1, p[i])
            pos_sum += p[i]
        else:
            mf.add_edge(i+1, T, -p[i])

    for _ in range(M):
        u, v = map(int, input().split())
        mf.add_edge(u, v, INF)

    for k in range(K):
        a, b = map(int, input().split())
        c = N + 1 + k
        pa = p[a-1] if p[a-1] > 0 else 0
        pb = p[b-1] if p[b-1] > 0 else 0
        cap = pa + pb
        mf.add_edge(a, c, INF)
        mf.add_edge(b, c, INF)
        mf.add_edge(c, T, cap)

    cut = mf.max_flow(S, T)
    print(pos_sum - cut)

main()

Step-by-Step 解説

1最大重みクロージャの定式化
「クロージャ」= 依存関係を満たす部分集合。最適値 = $\sum_{p_i > 0} p_i$ - 最小カット（= 最大流）。

2フローネットワークの構築
$s \to$ 正利益ノード（容量 $p_i$）、負利益ノード $\to t$（容量 $|p_i|$）、依存辺（容量 $\infty$）を設定。

3排他条件の補助ノード
補助ノード $c$ を介し $a \to c$、$b \to c$ に容量 $\infty$、$c \to t$ に両選択コストを設定。

4Dinic 法 $O(V^2 E)$
BFS でレベルグラフ構築 + DFS でブロッキングフロー探索。反復で最大流を求める。

5答えの計算
最大利益 = 正の利益の総和 - 最小カット。カットは「諦める正利益 + 引き受ける負コスト + 排他違反コスト」の最小和。

計算量

ノード数: $O(N + K)$
辺数: $O(N + M + K)$
Dinic: $O(V^2 E)$、実用上は高速
$N=500, M=2000, K=1000$ で十分実行可能

よくあるミス

ミス	原因	正しい書き方
依存辺の容量を有限にする	カットが依存辺を切ってしまう	依存辺は容量 $\infty$
逆辺の容量を 1 にする	残余グラフが不正	逆辺容量は必ず 0 で初期化
BFS で t に到達判定を忘れる	不要なループ	`return self.level[t] >= 0`
排他ノード番号の衝突	既存ノードと番号が重複	`c = N + 1 + k` で確実にずらす

次のステップ

発展問題: 3値分割問題（$s/t$ 以外に「中立」カテゴリがある最小カット）
関連: Day029 Q3 最大重みクロージャ基礎版
応用: 画像セグメンテーション（マルコフ確率場 + 最大流）

自己評価

完全理解おおむね理解要復習