結果
問題 | No.1316 Maximum Minimum Spanning Tree |
ユーザー |
![]() |
提出日時 | 2021-05-18 20:38:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 17 ms / 2,000 ms |
コード長 | 770 bytes |
コンパイル時間 | 2,539 ms |
コンパイル使用メモリ | 212,196 KB |
最終ジャッジ日時 | 2025-01-21 13:44:40 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 78 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/maxflow> using namespace std; using ll = long long; int main() { ll n, m, k; cin >> n >> m >> k; vector<array<ll, 5>> E(m); for (auto &[a, b, c, d, y] : E) cin >> a >> b >> c >> d; sort(E.begin(), E.end(), [] (auto x, auto y) { return x[2] < y[2]; }); int s = 0, t = n+1; ll ysum = 0, ans = 0; for (auto &[a, b, c, d, y] : E) { atcoder::mf_graph<ll> G(n+2); for (auto [a2, b2, c2, d2, y2] : E) { G.add_edge(s, a2, y2); G.add_edge(a2, b2, y2); } for (int v = 1; v <= n; ++v) G.add_edge(v, t, k); G.add_edge(s, a, k*n); G.add_edge(s, b, k*n); y = min(G.flow(s, t) - k - ysum, d); ysum += y; ans += c*y; } if (ysum < k*(n-1)) ans = -1; cout << ans << '\n'; }