結果
問題 |
No.3201 Corporate Synergy
|
ユーザー |
|
提出日時 | 2025-07-05 07:40:00 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 2,015 bytes |
コンパイル時間 | 1,444 ms |
コンパイル使用メモリ | 124,216 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-07-06 10:24:44 |
合計ジャッジ時間 | 2,288 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include <iostream> #include <vector> #include <numeric> #include <tuple> #include <atcoder/maxflow> using ll = long long; const ll INF = 2e12; // 安全な無限大の値 int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); // 1. 入力読み込み (修正版) int N, M, K; std::cin >> N; std::vector<ll> P(N + 1); for (int i = 1; i <= N; ++i) { std::cin >> P[i]; } std::cin >> M; std::vector<std::pair<int, int>> dependencies(M); for (int i = 0; i < M; ++i) { std::cin >> dependencies[i].first >> dependencies[i].second; } std::cin >> K; std::vector<std::tuple<int, int, ll>> partnerships(K); for (int i = 0; i < K; ++i) { std::cin >> std::get<0>(partnerships[i]) >> std::get<1>(partnerships[i]) >> std::get<2>(partnerships[i]); } // 2. グラフ構築 (変更なし) int S = 0, T = N + K + 1; atcoder::mf_graph<ll> graph(T + 1); for (int i = 1; i <= N; ++i) { if (P[i] > 0) { graph.add_edge(S, i, P[i]); } else { graph.add_edge(i, T, -P[i]); } } for (const auto& dep : dependencies) { graph.add_edge(dep.second, dep.first, INF); } for (int i = 0; i < K; ++i) { auto [u, v, s] = partnerships[i]; if (s > 0) { int 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. 総利益を直接計算 ll max_profit = 0; std::vector<bool> s_side = graph.min_cut(S); for (int i = 1; i <= N; ++i) { if (s_side[i]) { max_profit += P[i]; } } for (int i = 0; i < K; ++i) { auto [u, v, s] = partnerships[i]; if (s > 0 && s_side[u] && s_side[v]) { max_profit += s; } } std::cout << max_profit << std::endl; return 0; }