結果

問題 No.3201 Corporate Synergy
コンテスト
ユーザー YY-otter
提出日時 2025-07-03 08:47:32
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 3,967 bytes
コンパイル時間 1,258 ms
コンパイル使用メモリ 121,128 KB
実行使用メモリ 814,484 KB
最終ジャッジ日時 2025-07-06 10:24:49
合計ジャッジ時間 3,883 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 2
other RE * 4 MLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric>

// AtCoder Libraryからmaxflowをインクルード
#include <atcoder/maxflow>

using namespace std;

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, K;
    cin >> N >> M >> K;

    vector<long long> P(N);
    for (int i = 0; i < N; ++i) {
        cin >> P[i];
    }

    vector<pair<int, int>> dependencies(M);
    for (int i = 0; i < M; ++i) {
        cin >> dependencies[i].first >> dependencies[i].second;
        // 1-basedから0-basedへ変換
        dependencies[i].first--; 
        dependencies[i].second--;
    }

    vector<tuple<int, int, long long>> synergies(K);
    for (int i = 0; i < K; ++i) {
        cin >> get<0>(synergies[i]) >> get<1>(synergies[i]) >> get<2>(synergies[i]);
        // 1-basedから0-basedへ変換
        get<0>(synergies[i])--;
        get<1>(synergies[i])--;
    }

    // --- 最小カット問題のグラフ構築 ---

    // ノードの割り当て
    // 0..N-1: 都市ノード
    // N..N+K-1: 事業提携の補助ノード
    // N+K: ソースS
    // N+K+1: シンクT
    int S = N + K;
    int T = N + K + 1;
    atcoder::mf_graph<long long> mf(N + K + 2);

    // 事実上の無限大容量
    const long long INF = 1e18; 

    // 潜在的な利益の合計
    long long total_potential_profit = 0;

    // 1. 単独事業の利益/損失をモデル化
    for (int i = 0; i < N; ++i) {
        if (P[i] > 0) {
            // 正の利益: Sから都市ノードへの辺
            // この利益は得られる可能性がある
            total_potential_profit += P[i];
            mf.add_edge(S, i, P[i]);
        } else {
            // 負の利益 (損失): 都市ノードからTへの辺
            // このコストは発生する可能性がある
            mf.add_edge(i, T, -P[i]);
        }
    }

    // 2. 生産フロー (依存関係) をモデル化
    // U -> V (Vの事業にはUが必要)
    for (const auto& dep : dependencies) {
        int u = dep.first;
        int v = dep.second;
        // V を選ぶ(S側)ならUも選ばなければならない(S側)
        // V(S側) -> U(T側) というカットを禁止する
        mf.add_edge(v, u, INF);
    }

    // 3. 事業提携 (シナジー/ディスシナジー) をモデル化
    for (int j = 0; j < K; ++j) {
        int a = get<0>(synergies[j]);
        int b = get<1>(synergies[j]);
        long long s_val = get<2>(synergies[j]);
        int syn_node = N + j;

        if (s_val > 0) {
            // シナジー利益
            // この利益を得るためにはAとBの両方が必要
            total_potential_profit += s_val;
            
            // Sからシナジーノードへ、利益分の容量を持つ辺
            mf.add_edge(S, syn_node, s_val);
            
            // シナジーノードを選ぶなら、AとBも選ばなければならない
            mf.add_edge(syn_node, a, INF);
            mf.add_edge(syn_node, b, INF);
        } else {
            // ディスシナジー損失
            // AとBの両方を行うと、このコストが発生する
            long long cost = -s_val;
            
            // シナジーノードからTへ、コスト分の容量を持つ辺
            mf.add_edge(syn_node, T, cost);

            // AとBの両方を選ぶなら、シナジーノード(コスト)も受け入れなければならない
            mf.add_edge(a, syn_node, INF);
            mf.add_edge(b, syn_node, INF);
        }
    }

    // --- 計算と結果の出力 ---

    // SからTへの最大フローを計算 (これが最小カットのコストに等しい)
    long long min_cut_cost = mf.flow(S, T);

    // 最大利益 = (潜在的な利益の合計) - (最小カットコスト)
    long long max_profit = total_potential_profit - min_cut_cost;

    cout << max_profit << endl;

    return 0;
}
0