結果
問題 | No.654 Air E869120 |
ユーザー |
|
提出日時 | 2024-03-07 13:32:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,352 bytes |
コンパイル時間 | 2,507 ms |
コンパイル使用メモリ | 218,756 KB |
最終ジャッジ日時 | 2025-02-20 01:40:49 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 19 WA * 16 |
ソースコード
// STLのインクルード #include <bits/stdc++.h> using namespace std; // // ACLのインクルード(デフォルトはコメントアウト) // #include <atcoder/all> // using namespace atcoder; // for文の略記 #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define per(i, n) for (ll i = (ll)(n-1); i >= 0; i--) // vectorのソート #define all(x) x.begin(), x.end() // 型の略記 (競プロならでは) using ll = long long; using pii = pair<ll, ll>; using pll = pair<long long, long long>; using vi = vector<ll>; using vl = vector<long long>; using vs = vector<string>; using vc = vector<char>; using vpii = vector<pair<ll, ll>>; using vpll = vector<pair<long long, long long>>; using vpsi = vector<pair<string, ll>>; using vvi = vector<vector<ll>>; using vvpii = vector<vector<pair<ll, ll>>>; using vvl = vector<vector<long long>>; using vvc = vector<vector<char>>; template<typename T> using priority_queue_up = priority_queue<T, vector<T>, greater<T>>; // MOD計算で使う #define MOD 1000000007 #define MOD2 998244353 // YES-NOで答える質問で使う(fがTrueならYes) void cout_yn(bool f){ if(f)cout << "Yes" << endl; else cout << "No" << endl; } // 木の前順走査 void dfs_preorder(ll v, vvi &tree, vi &output){ output.push_back(v); rep(i, tree[v].size()){ dfs_preorder(tree[v][i], tree, output); } } // 木の後順走査 void dfs_postorder(ll v, vvi &tree, vi &output){ rep(i, tree[v].size()){ dfs_preorder(tree[v][i], tree, output); } output.push_back(v); } // n頂点m辺の無向グラフを隣接リストで受け取る. // 頂点番号は1-indexedとして入力される想定. vector<vector<ll>> input_undir_graph(ll n, ll m){ ll a, b; vector<vector<ll>> g(n); rep(i, m){ cin >> a >> b; a--, b--; g[a].push_back(b); // a->b へ向かう辺 g[b].push_back(a); // b->a へ向かう辺 } return g; } // n頂点m辺の有向グラフを隣接リストで受け取る. // 頂点番号は1-indexedとして入力される想定. vector<vector<ll>> input_dir_graph(ll n, ll m){ ll a, b; vector<vector<ll>> g(n); rep(i, m){ cin >> a >> b; a--, b--; g[a].push_back(b); // a->b へ向かう辺 } return g; } #define INF 1e18 struct edge{ ll to, cap, p, q, rev; }; vector<vector<edge>> G; vector<map<ll, ll>> used; ll n, m; ll d; void add_edge(ll u, ll v, ll c, ll p, ll q){ G[u].push_back((edge){v, c, p, q, (ll)(G[v].size())}); G[v].push_back((edge){u, 0, q, p, (ll)(G[u].size()-1)}); } ll dfs(ll v, ll p, ll t, ll tq, ll f){ if(v == t && p == tq){ return f; } used[v][p] = 1; vector<edge> &E = G[v]; rep(i, E.size()){ edge &e = E[i]; if(e.p != p)continue; if(e.cap > 0 && !used[e.to][e.q]){ ll w = dfs(e.to, e.q, t, tq, min(f, e.cap)); if(w > 0){ e.cap -= w; G[e.to][e.rev].cap += w; return w; } } } return 0; } ll max_flow(ll s, ll p, ll t, ll tq){ ll flow = 0; int cnt = 0; for(;;){ for(ll i=0; i<n; i++)used[i].clear(); ll f = dfs(s, p, t, tq, INF); if(f == 0)break; flow += f; cnt++; /* cout << flow << endl; */ } return flow; } // main関数 int main(void){ cin >> n >> m >> d; vector<set<ll>> time(n); G.resize(n); used.resize(n); ll u, v, p, q, w; rep(i, m){ cin >> u >> v >> p >> q >> w; u--, v--; add_edge(u, v, w, p, q+d); time[u].insert(p); time[v].insert(q+d); } rep(i, n){ if(time[i].size() <= 1)continue; for(auto itr=time[i].begin(); itr!=(--time[i].end()); itr++){ auto nx = itr; nx++; add_edge(i, i, INF, *itr, *nx); } } if(time[0].size() == 0 || time[n-1].size() == 0){ cout << 0 << endl; return 0; } /* rep(i, n){ */ /* cout << i+1 << endl; */ /* rep(j, G[i].size()){ */ /* cout << "\t" << G[i][j].to << " " << G[i][j].cap << " " << G[i][j].p << " " << G[i][j].q << " " << G[i][j].rev << endl; */ /* } */ /* } */ cout << max_flow(0, *time[0].begin(), n-1, *(--(time[n-1].end()))) << endl; return 0; }