結果
問題 |
No.3201 Corporate Synergy
|
ユーザー |
|
提出日時 | 2025-07-12 17:50:47 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,136 bytes |
コンパイル時間 | 1,341 ms |
コンパイル使用メモリ | 116,760 KB |
実行使用メモリ | 7,848 KB |
最終ジャッジ日時 | 2025-07-12 17:50:50 |
合計ジャッジ時間 | 2,420 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 WA * 10 |
ソースコード
#include <iostream> #include <vector> #include <atcoder/maxflow> constexpr int64_t INF = 1LL << 40; 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] - 1] && selected[B[i] - 1]) profit += S[i]; } std::cout << profit << std::endl; }