結果
問題 | No.654 Air E869120 |
ユーザー | goto_isyuku |
提出日時 | 2020-10-07 00:25:59 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 8 ms / 2,000 ms |
コード長 | 4,301 bytes |
コンパイル時間 | 2,749 ms |
コンパイル使用メモリ | 195,048 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-20 03:07:07 |
合計ジャッジ時間 | 4,477 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
6,812 KB |
testcase_01 | AC | 3 ms
6,940 KB |
testcase_02 | AC | 3 ms
6,944 KB |
testcase_03 | AC | 3 ms
6,944 KB |
testcase_04 | AC | 3 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 3 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 3 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 7 ms
6,940 KB |
testcase_11 | AC | 7 ms
6,940 KB |
testcase_12 | AC | 6 ms
6,940 KB |
testcase_13 | AC | 8 ms
6,940 KB |
testcase_14 | AC | 6 ms
6,944 KB |
testcase_15 | AC | 6 ms
6,944 KB |
testcase_16 | AC | 7 ms
6,940 KB |
testcase_17 | AC | 8 ms
6,944 KB |
testcase_18 | AC | 7 ms
6,944 KB |
testcase_19 | AC | 7 ms
6,944 KB |
testcase_20 | AC | 5 ms
6,940 KB |
testcase_21 | AC | 5 ms
6,940 KB |
testcase_22 | AC | 5 ms
6,940 KB |
testcase_23 | AC | 5 ms
6,944 KB |
testcase_24 | AC | 6 ms
6,944 KB |
testcase_25 | AC | 5 ms
6,940 KB |
testcase_26 | AC | 6 ms
6,940 KB |
testcase_27 | AC | 5 ms
6,940 KB |
testcase_28 | AC | 5 ms
6,944 KB |
testcase_29 | AC | 5 ms
6,940 KB |
testcase_30 | AC | 5 ms
6,944 KB |
testcase_31 | AC | 4 ms
6,944 KB |
testcase_32 | AC | 4 ms
6,944 KB |
testcase_33 | AC | 4 ms
6,944 KB |
testcase_34 | AC | 4 ms
6,944 KB |
testcase_35 | AC | 2 ms
6,940 KB |
testcase_36 | AC | 2 ms
6,940 KB |
testcase_37 | AC | 2 ms
6,944 KB |
testcase_38 | AC | 2 ms
6,944 KB |
testcase_39 | AC | 2 ms
6,940 KB |
ソースコード
#include <bits/stdc++.h> #define rep(X, N) for (ll X = 0LL; X < (N); X++) #define ALL(V) (V).begin(), (V).end() #define endl "\n" using namespace std; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; const double PI = 3.1415926535897932384626; const ll MODN = 1000000007; const ll MODN2 = 998244353; // Dinic法を用いた最大流を求めるクラス // 容量を表す型 typedef ll Cap; Cap zero(){ return 0; } Cap inf(){ return LLONG_MAX; } class Edge{ public: int to, revIndex; Cap cap; Edge(int t, Cap c, int revi){ to = t; cap = c; revIndex = revi; } }; class MaxFlow{ public: vector<vector<Edge>> graph; vector<int> fromStart; vector<int> iter; vector<int> zeros; vector<int> minus; MaxFlow(){} MaxFlow(int n){ vector<Edge> tmpv; for(int i = 0; i < n; i++){ graph.push_back(tmpv); zeros.push_back(0); minus.push_back(-1); } } void addEdge(int from, int to, Cap cap){ graph[from].push_back(Edge(to, cap, (int)graph[to].size())); graph[to].push_back(Edge(from, zero(), (int)graph[from].size() - 1)); } void bfs(int s){ fromStart = minus; queue<int> q; fromStart[s] = 0; q.push(s); while(!q.empty()){ int v = q.front(); q.pop(); for(int i = 0; i < graph[v].size(); i++){ Edge &e = graph[v][i]; if(e.cap > zero() && fromStart[e.to] < 0){ fromStart[e.to] = fromStart[v] + 1; q.push(e.to); } } } } Cap dfs(int s, int t, Cap f){ if(s == t) return f; for(int &i = iter[s]; i < graph[s].size(); i++){ Edge &e = graph[s][i]; if(e.cap > zero() && fromStart[s] < fromStart[e.to]){ Cap d = dfs(e.to, t, min(f, e.cap)); if(d > zero()){ e.cap -= d; graph[e.to][e.revIndex].cap += d; return d; } } } return zero(); } Cap solve(int start, int end){ Cap flow = zero(); while(true){ bfs(start); if(fromStart[end] < 0) return flow; iter = zeros; Cap f = dfs(start, end, inf()); while(f > zero()){ flow += f; f = dfs(start, end, inf()); } } } }; class Flight{ public: int u,v,p,q; ll w; Flight(int _u, int _v, int _p, int _q, ll _w){ u = _u; v = _v; p = _p; q = _q; w = _w; } }; int main(){ int n,m,d; cin >> n >> m >> d; vector<Flight> flight; vector<vector<pair<int, int>>> node(n + 1); int count = 0; rep(i, m){ int u, v, p, q; ll w; cin >> u >> v >> p >> q >> w; flight.push_back(Flight(u, v, p, q, w)); count++; node[u].push_back(make_pair(p, count)); //cerr << count << " " << u << " " << p << endl; count++; node[v].push_back(make_pair(q + d, count)); //cerr << count << " " << v << " " << q + d << endl; } for(int i = 1; i <= n ; i++){ sort(ALL(node[i])); } // count + 1がsinkになる MaxFlow mf(count + 2); for(Flight f : flight){ auto itr = lower_bound(node[f.u].begin(), node[f.u].end(), make_pair(f.p, 0)); assert(itr != node[f.u].end()); int uidx = itr - node[f.u].begin(); itr = lower_bound(node[f.v].begin(), node[f.v].end(), make_pair(f.q + d, 0)); if(itr != node[f.v].end()){ int vidx = itr - node[f.v].begin(); mf.addEdge(node[f.u][uidx].second, node[f.v][vidx].second, f.w); } } for(int i = 1; i <= n; i++){ for(int j = 0; j + 1 < node[i].size(); j++){ mf.addEdge(node[i][j].second, node[i][j + 1].second, inf()); } } for(int i = 0; i < node[1].size(); i++){ mf.addEdge(0, node[1][i].second, inf()); } for(int i = 0; i < node[n].size(); i++){ mf.addEdge(node[n][i].second, count + 1, inf()); } cout << mf.solve(0, count + 1) << endl; return 0; }