結果

問題 No.3201 Corporate Synergy
ユーザー YY-otter
提出日時 2025-07-03 16:58:13
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 5,444 bytes
コンパイル時間 1,405 ms
コンパイル使用メモリ 81,796 KB
実行使用メモリ 68,296 KB
最終ジャッジ日時 2025-07-06 10:24:53
合計ジャッジ時間 3,659 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 2
other RE * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

# g.py
import sys
from collections import deque

# Pythonの再帰深度の上限を増やす（Dinic法のDFSで必要になる場合がある）
sys.setrecursionlimit(10**6)

class MaxFlowDinic:
    """
    Dinic法による最大フローアルゴリズムの実装。
    """
    def __init__(self, n: int):
        """
        Args:
            n (int): グラフの頂点数。
        """
        self.n = n
        # グラフの隣接リスト表現
        # 各要素は [行き先, 容量, 逆辺のインデックス]
        self.graph = [[] for _ in range(n)]
        self.level = [-1] * n
        self.iter = [0] * n
        self.INF = 10**18  # 十分に大きい数

    def add_edge(self, u: int, v: int, cap: int):
        """
        頂点uからvへ容量capの辺を追加する。
        同時に、容量0の逆辺も追加する。

        Args:
            u (int): 辺の始点。
            v (int): 辺の終点。
            cap (int): 辺の容量。
        """
        # 順方向の辺
        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: int):
        """
        BFSを用いて、ソースsからのレベルグラフ（各頂点の距離）を構築する。
        """
        self.level = [-1] * self.n
        q = deque([s])
        self.level[s] = 0
        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)

    def _dfs(self, v: int, t: int, f: int) -> int:
        """
        DFSを用いて、vからtへ流せるフロー(ブロッキングフロー)を探す。
        """
        if v == t:
            return f
        
        # iter[v]以降の辺を探索（探索済みの辺をスキップする高速化）
        while self.iter[v] < len(self.graph[v]):
            edge = self.graph[v][self.iter[v]]
            to, cap, rev_idx = edge
            
            if cap > 0 and self.level[v] < self.level[to]:
                # 再帰的にフローを流す
                d = self._dfs(to, t, min(f, cap))
                if d > 0:
                    # 辺の容量を更新
                    edge[1] -= d
                    self.graph[to][rev_idx][1] += d
                    return d
            self.iter[v] += 1
            
        return 0

    def get_max_flow(self, s: int, t: int) -> int:
        """
        ソースsからシンクtへの最大フローを計算する。
        """
        flow = 0
        while True:
            self._bfs(s)
            # シンクtに到達できなくなったら終了
            if self.level[t] < 0:
                return flow
            self.iter = [0] * self.n
            while True:
                f = self._dfs(s, t, self.INF)
                if f == 0:
                    break
                flow += f
    
    def min_cut(self, s: int) -> list[bool]:
        """
        最小カットを計算し、S側の頂点集合を返す。
        最大フロー計算後の残余グラフで、Sから到達可能な頂点を探索する。
        """
        visited = [False] * self.n
        q = deque([s])
        visited[s] = True
        while q:
            v = q.popleft()
            for to, cap, _ in self.graph[v]:
                if cap > 0 and not visited[to]:
                    visited[to] = True
                    q.append(to)
        return visited

def g_solver():
    """
    メインの処理。
    """
    # 高速入出力
    input = sys.stdin.readline

    # 1. 入力読み込み
    N, M, K = map(int, input().split())
    P = [0] + list(map(int, input().split()))
    dependencies = [tuple(map(int, input().split())) for _ in range(M)]
    partnerships = [tuple(map(int, input().split())) for _ in range(K)]

    # 2. グラフ構築
    S, T = 0, N + K + 1
    # 自作のMaxFlowDinicクラスを使用
    mf = MaxFlowDinic(T + 1)
    
    # 都市の利益/コストに応じて、S/Tとの辺を張る
    for i in range(1, N + 1):
        if P[i] > 0:
            mf.add_edge(S, i, P[i])
        else:
            mf.add_edge(i, T, -P[i])
    
    # 依存関係の辺を張る
    for u, v in dependencies:
        mf.add_edge(v, u, mf.INF)

    # 提携に関する辺を張る
    for i in range(K):
        u, v, s = partnerships[i]
        p_node = N + 1 + i
        if s > 0:
            mf.add_edge(S, p_node, s)
            mf.add_edge(p_node, u, mf.INF)
            mf.add_edge(p_node, v, mf.INF)
        else:
            mf.add_edge(p_node, T, -s)
            mf.add_edge(u, p_node, mf.INF)
            mf.add_edge(v, p_node, mf.INF)

    # 3. 最小カットを計算（最大フローを求める）
    mf.get_max_flow(S, T)

    # 4. 最適な事業選択を特定し、総利益を計算する
    max_profit = 0
    s_side = mf.min_cut(S) # S側の頂点集合を取得

    # S側にある（=選択された）都市の利益を合計
    for i in range(1, N + 1):
        if s_side[i]:
            max_profit += P[i]

    # 提携の条件を満たすものの利益/コストを合計
    for u, v, s in partnerships:
        if s_side[u] and s_side[v]:
            max_profit += s
            
    print(max_profit)


if __name__ == '__main__':
    g_solver()
0