結果

問題 No.3201 Corporate Synergy
コンテスト
ユーザー fdironia
提出日時 2025-08-14 20:16:18
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 1,270 bytes
コンパイル時間 1,124 ms
コンパイル使用メモリ 115,200 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-14 20:16:21
合計ジャッジ時間 2,209 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using namespace std;
using namespace atcoder;

using ll = long long;

constexpr int N = 200;
constexpr int P = 1e9;
constexpr ll INF = 2ll * N * P + 1; 

int main() {
    int n;
    cin >> n;
    int p[n];
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    int m;
    cin >> m;
    int u[m], v[m];
    for (int i = 0; i < m; i++) {
        cin >> u[i] >> v[i];
        u[i]--; v[i]--;
    }
    int k;
    cin >> k;
    int a[k], b[k], s[k];
    for (int i = 0; i < k; i++) {
        cin >> a[i] >> b[i] >> s[i];
        a[i]--; b[i]--;
    }

    ll ans = 0;
    mf_graph<ll> g(n + k + 2);

    for (int i = 0; i < n; i++) {
        if (p[i] >= 0) {
            ans += p[i];
            g.add_edge(n + k, i, p[i]);
            g.add_edge(i, n + k + 1, 0);
        } else {
            g.add_edge(n + k, i, 0);
            g.add_edge(i, n + k + 1, -p[i]);
        }
    }

    for (int i = 0; i < m; i++) {
        g.add_edge(v[i], u[i], INF);
    }

    for (int i = 0; i < k; i++) {
        ans += s[i];
        g.add_edge(n + k, n + i, s[i]);
        g.add_edge(n + i, a[i], INF);
        g.add_edge(n + i, b[i], INF);
    }

    ans -= g.flow(n + k, n + k + 1);
    cout << ans << endl;

    return 0;
}
0