結果
問題 | No.654 Air E869120 |
ユーザー | NAMIDAIRO |
提出日時 | 2024-04-24 02:01:07 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 20 ms / 2,000 ms |
コード長 | 2,951 bytes |
コンパイル時間 | 1,552 ms |
コンパイル使用メモリ | 116,584 KB |
実行使用メモリ | 34,872 KB |
最終ジャッジ日時 | 2024-11-06 08:40:49 |
合計ジャッジ時間 | 3,112 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,820 KB |
testcase_03 | AC | 2 ms
6,816 KB |
testcase_04 | AC | 2 ms
6,816 KB |
testcase_05 | AC | 3 ms
6,816 KB |
testcase_06 | AC | 2 ms
6,816 KB |
testcase_07 | AC | 2 ms
6,816 KB |
testcase_08 | AC | 2 ms
6,816 KB |
testcase_09 | AC | 2 ms
6,820 KB |
testcase_10 | AC | 9 ms
6,820 KB |
testcase_11 | AC | 8 ms
6,816 KB |
testcase_12 | AC | 7 ms
6,816 KB |
testcase_13 | AC | 8 ms
6,816 KB |
testcase_14 | AC | 8 ms
6,816 KB |
testcase_15 | AC | 8 ms
6,820 KB |
testcase_16 | AC | 12 ms
6,816 KB |
testcase_17 | AC | 14 ms
6,820 KB |
testcase_18 | AC | 12 ms
6,820 KB |
testcase_19 | AC | 12 ms
6,816 KB |
testcase_20 | AC | 8 ms
6,820 KB |
testcase_21 | AC | 8 ms
6,820 KB |
testcase_22 | AC | 6 ms
6,816 KB |
testcase_23 | AC | 7 ms
6,816 KB |
testcase_24 | AC | 8 ms
6,820 KB |
testcase_25 | AC | 6 ms
6,816 KB |
testcase_26 | AC | 7 ms
6,816 KB |
testcase_27 | AC | 6 ms
6,816 KB |
testcase_28 | AC | 6 ms
6,820 KB |
testcase_29 | AC | 6 ms
6,820 KB |
testcase_30 | AC | 20 ms
34,872 KB |
testcase_31 | AC | 19 ms
34,832 KB |
testcase_32 | AC | 18 ms
34,868 KB |
testcase_33 | AC | 18 ms
34,840 KB |
testcase_34 | AC | 19 ms
34,844 KB |
testcase_35 | AC | 2 ms
6,816 KB |
testcase_36 | AC | 2 ms
6,820 KB |
testcase_37 | AC | 2 ms
6,816 KB |
testcase_38 | AC | 2 ms
6,816 KB |
testcase_39 | AC | 2 ms
6,816 KB |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <queue> #include <set> #include <iomanip> using namespace std; typedef long long ll; #define rep(i, n) for(int i = 0; i < (n); i++) template<class T> using vi = vector<T>; template<class T> using vii = vector<vi<T>>; template<class T> using viii = vector<vii<T>>; struct Dinic { private: const long long inf = 1e18; vector<int> dist; //sからの距離 vector<int> iter; //どこまで調べたか public: struct edge { int to, rev; long long cap; edge(int t = 0, int r = 0, long long c = 0LL) : to(t), rev(r), cap(c) {} }; int n; vector<vector<edge>> to; Dinic(int n_ = 1) : n(n_), to(n_), dist(n_), iter(n_) {} void addedge(int u, int v, long long cap) {//u->vにcapの容量 int su = (int)to[u].size(), sv = (int)to[v].size(); to[u].push_back({ v, sv, cap }); to[v].push_back({ u, su, 0 }); } long long dfs(int v, int t, long long f) { //t: 終点, f: flow if (v == t) return f; int sv = (int)to[v].size(); for (int& i = iter[v]; i < sv; i++) { edge& nv = to[v][i]; if (dist[nv.to] <= dist[v] || nv.cap == 0) continue; //here?? long long nf = dfs(nv.to, t, min(f, nv.cap)); if (nf > 0) { nv.cap -= nf; to[nv.to][nv.rev].cap += nf; return nf; } } return 0; } void bfs(int s) { dist.assign(n, -1); queue<int> q; q.push(s); dist[s] = 0; while (!q.empty()) { int v = q.front(); q.pop(); for (auto nv : to[v]) { if (nv.cap > 0 && dist[nv.to] < 0) { dist[nv.to] = dist[v] + 1; q.push(nv.to); } } } } long long maxflow(int s, int t) {//s:始点, t:終点 long long res = 0, flow = 0; while (true) { bfs(s); if (dist[t] < 0) break; iter.assign(n, 0); while (flow = dfs(s, t, inf)) res += flow; }; return res; } }; int main() { int n, m, d; cin >> n >> m >> d; vi<int> u(m), v(m), p(m), q(m); vi<ll> w(m); rep(i, m) cin >> u[i] >> v[i] >> p[i] >> q[i] >> w[i]; rep(i, m) u[i]--, v[i]--; rep(i, m) q[i] += d; vi<map<int, int>> mp(n); rep(i, m) { mp[u[i]][p[i]]; mp[v[i]][q[i]]; } const ll inf = 1e18; Dinic ff(n * m); int idx = 0; rep(i, n) { bool ng = true; for (auto& elem : mp[i]) { elem.second = idx; if (ng) ng = false; else ff.addedge(idx - 1, idx, inf); idx++; } } rep(i, m) ff.addedge(mp[u[i]][p[i]], mp[v[i]][q[i]], w[i]); ll res = ff.maxflow(0, idx - 1); cout << res << endl; return 0; }