結果

問題 No.3201 Corporate Synergy
ユーザー iastm
提出日時 2025-07-12 17:54:59
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,128 bytes
コンパイル時間 1,626 ms
コンパイル使用メモリ 115,956 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-07-12 17:55:02
合計ジャッジ時間 2,334 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <atcoder/maxflow>

constexpr int64_t INF = 1LL << 60;

int main() {
    atcoder::mf_graph<int64_t> graph(402);
    int N;
    std::cin >> N;
    std::vector<int> P(N);
    for (int i = 0; i < N; i++) {
        std::cin >> P[i];
        if (P[i] > 0) graph.add_edge(0, i + 1, P[i]);
        else graph.add_edge(i + 1, 401, -P[i]);
    }
    int M;
    std::cin >> M;
    for (int i = 0; i < M; i++) {
        int U, V;
        std::cin >> U >> V;
        graph.add_edge(V, U, INF);
    }
    int K;
    std::cin >> K;
    std::vector<int> A(K), B(K), S(K);
    for (int i = 0; i < K; i++) {
        std::cin >> A[i] >> B[i] >> S[i];
        graph.add_edge(0, i + 201, S[i]);
        graph.add_edge(i + 201, A[i], INF);
        graph.add_edge(i + 201, B[i], INF);
    }
    graph.flow(0, 401);
    auto selected = graph.min_cut(0);
    int64_t profit = 0;
    for (int i = 0; i < N; i++) {
        if (selected[i + 1]) profit += P[i];
    }
    for (int i = 0; i < K; i++) {
        if (selected[A[i]] && selected[B[i]]) profit += S[i];
    }
    std::cout << profit << std::endl;
}
0