結果

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

ソースコード

diff # 

# g.py
import sys
from atcoder.maxflow import MFGraph

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

    # 1. 入力読み込み
    N, M, K = map(int, input().split())

    # 都市の利益P。1-indexedで扱うため、先頭にダミー要素を追加。
    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. グラフ構築
    # 頂点ID:
    #   S (ソース): 0
    #   都市: 1 to N
    #   提携: N+1 to N+K
    #   T (シンク): N+K+1
    S, T = 0, N + K + 1
    graph = MFGraph(T + 1)
    
    INF = 10**18  # 十分に大きい数（無限大と見なす）

    # 都市の利益/コストに応じて、S/Tとの辺を張る
    for i in range(1, N + 1):
        if P[i] > 0:
            # 利益がある場合はSから都市へ辺を張る
            graph.add_edge(S, i, P[i])
        else:
            # コストがかかる場合は都市からTへ辺を張る
            graph.add_edge(i, T, -P[i])
    
    # 依存関係の辺を張る (u を選ぶなら v も選ぶ -> vからuへ容量INFの辺)
    for u, v in dependencies:
        graph.add_edge(v, u, INF)

    # 提携に関する辺を張る
    for i in range(K):
        u, v, s = partnerships[i]
        p_node = N + 1 + i # 提携を表す補助ノード
        if s > 0:
            # 利益sを得る提携 (uとvの両方を選ぶと利益s)
            graph.add_edge(S, p_node, s)
            graph.add_edge(p_node, u, INF)
            graph.add_edge(p_node, v, INF)
        else:
            # コスト-sを支払う提携 (uとvの両方を選ぶとコスト-s)
            graph.add_edge(p_node, T, -s)
            graph.add_edge(u, p_node, INF)
            graph.add_edge(v, p_node, INF)

    # 3. 最小カットを計算
    # 最大フローを計算することで、暗に最小カットが求まる
    graph.flow(S, T)

    # 4. 最適な事業選択を特定し、定義通りに総利益を直接計算する
    max_profit = 0
    # min_cut(S)はS側に属する頂点のboolリストを返す
    s_side = graph.min_cut(S)

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

    # 提携の条件（uとvの両方がS側にある）を満たすものの利益/コストを合計
    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