結果

問題 No.3201 Corporate Synergy
コンテスト
ユーザー YY-otter
提出日時 2025-07-05 07:57:13
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 120 ms / 2,000 ms
コード長 4,525 bytes
コンパイル時間 256 ms
コンパイル使用メモリ 82,308 KB
実行使用メモリ 77,416 KB
最終ジャッジ日時 2025-07-06 10:24:59
合計ジャッジ時間 2,735 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

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

class MaxFlow:
    """Dinic法による最大流アルゴリズムを実装したクラス"""
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.level = [-1] * n
        self.iter = [0] * n
        self.inf = float('inf')

    def add_edge(self, u, v, cap):
        # 順方向の辺と、容量0の逆方向の辺を追加
        # graph[u] = [(to, capacity, reverse_edge_index_in_v's_adj_list)]
        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):
        """始点sからの距離を計算し、レベルグラフを構築する"""
        self.level = [-1] * self.n
        q = deque([s])
        self.level[s] = 0
        while q:
            u = q.popleft()
            for i, (v, cap, rev) in enumerate(self.graph[u]):
                if cap > 0 and self.level[v] < 0:
                    self.level[v] = self.level[u] + 1
                    q.append(v)
        return self.level

    def _dfs(self, v, t, f):
        """レベルグラフ上でs-tパスを見つけ、フローを流す"""
        if v == t:
            return f
        
        # iter[v]から探索することで、探索済みの辺をスキップし高速化
        for i in range(self.iter[v], len(self.graph[v])):
            self.iter[v] = i
            to, cap, rev = self.graph[v][i]
            if cap > 0 and self.level[v] < self.level[to]:
                d = self._dfs(to, t, min(f, cap))
                if d > 0:
                    self.graph[v][i][1] -= d
                    self.graph[to][rev][1] += d
                    return d
        return 0

    def flow(self, s, t):
        """始点sから終点tへの最大流を求める"""
        max_flow = 0
        while True:
            self._bfs(s)
            if self.level[t] < 0:
                # 終点tに到達できなくなったら終了
                return max_flow
            self.iter = [0] * self.n
            f = self._dfs(s, t, self.inf)
            while f > 0:
                max_flow += f
                f = self._dfs(s, t, self.inf)
    
    def min_cut_s_side(self, s):
        """最大流を計算した後の残余グラフで、sから到達可能なノード集合を返す"""
        s_side = [False] * self.n
        q = deque([s])
        s_side[s] = True
        while q:
            u = q.popleft()
            for v, cap, rev in self.graph[u]:
                if cap > 0 and not s_side[v]:
                    s_side[v] = True
                    q.append(v)
        return s_side


def solve():
    input = sys.stdin.readline

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

    # 2. グラフの構築
    S, T = 0, N + K + 1
    graph = MaxFlow(T + 1)
    # INFは全てのありうる利益の合計よりも十分に大きい値
    INF = (N + K) * 10**9 + 1 

    # 単独事業の損益
    for i in range(N):
        node_id = i + 1
        profit = P[i]
        if profit > 0:
            graph.add_edge(S, node_id, profit)
        else:
            graph.add_edge(node_id, T, -profit)
    
    # 生産フロー (依存関係)
    for u, v in dependencies:
        graph.add_edge(v, u, INF)

    # 事業提携 (シナジーのみ)
    for i in range(K):
        u, v, s = partnerships[i]
        if s > 0:
            p_node = N + 1 + i
            graph.add_edge(S, p_node, s)
            graph.add_edge(p_node, u, INF)
            graph.add_edge(p_node, v, INF)
    
    # 3. 最大流（=最小カット）を計算
    graph.flow(S, T)

    # 4. 最適な事業選択を特定し、定義通りに総利益を直接計算
    max_profit = 0
    s_side = graph.min_cut_s_side(S)

    # S側にある都市のP_iを合計
    for i in range(N):
        node_id = i + 1
        if s_side[node_id]:
            max_profit += P[i]
            
    # S側にある提携のS_jを合計
    for i in range(K):
        u, v, s = partnerships[i]
        if s > 0: # シナジーのみ考慮
            if s_side[u] and s_side[v]:
                max_profit += s
    
    print(max_profit)

solve()
0