結果
問題 | No.119 旅行のツアーの問題 |
ユーザー | eiuru |
提出日時 | 2024-04-03 15:43:48 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 2,568 bytes |
コンパイル時間 | 2,849 ms |
コンパイル使用メモリ | 218,980 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-09-30 23:58:45 |
合計ジャッジ時間 | 3,251 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 2 ms
6,816 KB |
testcase_03 | AC | 2 ms
6,820 KB |
testcase_04 | AC | 2 ms
6,820 KB |
testcase_05 | AC | 2 ms
6,820 KB |
testcase_06 | AC | 2 ms
6,820 KB |
testcase_07 | AC | 2 ms
6,816 KB |
testcase_08 | AC | 2 ms
6,820 KB |
testcase_09 | AC | 2 ms
6,820 KB |
testcase_10 | AC | 2 ms
6,820 KB |
testcase_11 | AC | 2 ms
6,820 KB |
testcase_12 | AC | 2 ms
6,820 KB |
testcase_13 | AC | 2 ms
6,816 KB |
testcase_14 | AC | 2 ms
6,820 KB |
testcase_15 | AC | 2 ms
6,820 KB |
testcase_16 | AC | 2 ms
6,820 KB |
testcase_17 | AC | 2 ms
6,824 KB |
testcase_18 | AC | 2 ms
6,816 KB |
testcase_19 | AC | 2 ms
6,820 KB |
testcase_20 | AC | 2 ms
6,820 KB |
testcase_21 | AC | 2 ms
6,816 KB |
testcase_22 | AC | 2 ms
6,820 KB |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i=0; i<n; ++i) using namespace std; using ll = long long; template <class C> struct Flow { private: int n; vector<pair<int,int>> p; vector<vector<tuple<int,int,C>>> g; public: Flow(int n):n(n),g(n){} struct E { int u, v; C c, f; }; int add(int u, int v, C c) { int ui = int(g[u].size()); int vi = int(g[v].size()); if (u==v) ++vi; p.emplace_back(u,ui); g[u].emplace_back(v,vi,c); g[v].emplace_back(u,ui,0); return int(p.size()) - 1; } E getEdge(int i) { auto&[v,vi,cv] = g[p[i].first][p[i].second]; auto&[u,ui,cu] = g[v][vi]; return E{u, v, cu+cv, cu}; } void changeEdge(int i, C c, C f) { auto&[v,vi,cv] = g[p[i].first][p[i].second]; auto&[u,ui,cu] = g[v][vi]; cv = c - f; cu = f; } C flow(int s, int t, C flow = numeric_limits<C>::max()) { vector<int> depth(n); auto bfs = [&]{ fill(depth.begin(), depth.end(), -1); depth[s] = 0; queue<int> q; q.push(s); while(q.size()){ int u = q.front(); q.pop(); for (auto [v,vi,c]:g[u]) { if (c==0 || depth[v]>=0) continue; depth[v] = depth[u]+1; if(v==t) return true; q.push(v); } } return false; }; function<C(int,C)> dfs = [&](int v, C up){ if(v==s) return up; C res = 0; for(auto&[u,ui,cu]:g[v]){ auto&[_,vi,cv] = g[u][ui]; if (depth[v]<=depth[u]||cv==0) continue; C f = dfs(u, min(up-res, cv)); if (f<=0) continue; cu += f; cv -= f; res += f; if (res == up) return res; } depth[v] = n; return res; }; C res = 0; while(flow && bfs()){ C f = dfs(t,flow); flow -= f; res += f; } return res; } vector<bool> cut(int s) { vector<bool> res(n); queue<int> q; q.push(s); while (q.size()) { int u = q.front(); q.pop(); res[u] = true; for(auto&[v,vi,c]:g[u]){ if (c&&!res[v]) { res[v] = true; q.push(v); } } } return res; } }; int n,m,b,c,d,e; int f(int i,int j){ return i*2+j; } int main() { cin >> n; int s = n*2, t = s+1; Flow<ll> v(t+1); ll ans = 0; rep(i,n){ cin >> b >> c; ans += b+c; v.add(s,f(i,0),b); v.add(f(i,0),f(i,1),b+c); v.add(f(i,1),t,c); v.add(f(i,1),f(i,0),1e9); } cin >> m; rep(_,m){ cin >> d >> e; v.add(f(d,1),f(e,0),1e9); } ans -= v.flow(s,t); cout << ans << endl; }