結果
問題 | No.119 旅行のツアーの問題 |
ユーザー | momoyuu |
提出日時 | 2022-09-30 23:16:42 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,883 bytes |
コンパイル時間 | 2,708 ms |
コンパイル使用メモリ | 254,176 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-02 06:40:50 |
合計ジャッジ時間 | 3,579 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | AC | 1 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | AC | 2 ms
6,944 KB |
testcase_07 | AC | 1 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,944 KB |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | AC | 1 ms
6,940 KB |
testcase_12 | AC | 1 ms
6,940 KB |
testcase_13 | WA | - |
testcase_14 | AC | 1 ms
6,940 KB |
testcase_15 | AC | 1 ms
6,940 KB |
testcase_16 | AC | 2 ms
6,944 KB |
testcase_17 | AC | 1 ms
6,940 KB |
testcase_18 | AC | 2 ms
6,940 KB |
testcase_19 | AC | 1 ms
6,940 KB |
testcase_20 | WA | - |
testcase_21 | AC | 2 ms
6,944 KB |
testcase_22 | AC | 2 ms
6,940 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; template<class t> using vc = vector<t>; template<class t> using vvc = vc<vc<t>>; using pi = pair<int,int>; using pl = pair<ll,ll>; using vi = vc<int>; using vvi = vvc<int>; using vl = vc<ll>; using vvl = vvc<ll>; #define rep(i,a,b) for (int i = (int)(a); i < (int)(b); i++) #define irep(i,a,b) for (int i = (int)(a); i > (int)(b); i--) #define all(a) a.begin(),a.end() #define print(n) cout << n << '\n' #define pritn(n) print(n) #define printv(n,a) {copy(all(n),ostream_iterator<a>(cout," ")); cout<<"\n";} #define printvv(n,a) {for(auto itr:n) printv(itr,a);} #define rup(a,b) (a+b-1)/b #define input(A,N) rep(i,0,N) cin>>A[i] #define chmax(a,b) a = max(a,b) #define chmin(a,b) a = min(a,b) template< typename T > struct edge{ int from,to,rev; T cost; /* *to:繋がってる先 *cost:辺のコスト */ edge(int from,int to,int rev,T cost):from(from),to(to),rev(rev),cost(cost){}; edge &operator=(const int& x){ to = x; return *this; } }; template< typename T > struct graph{ int n; vector<vector<edge<T>>> e; graph(int n):n(n),e(n){} void addedge(int from,int to,T cost){ e[from].emplace_back(from,to,(int)e[to].size(),cost); e[to].emplace_back(to,from,(int)e[from].size()-1,0); } vector<edge<T>> &operator[](int i) { return e[i]; } }; template< typename T > struct FordFulkerson{ const int INF = (T)1e9; vector<int> vis; FordFulkerson(){}; T dfs(graph<T>&g,int ni,int t,T f){ if(ni==t) return f; vis[ni] = 1; for(auto &e:g[ni]){ if(vis[e.to]||e.cost<=0) continue; T d = dfs(g,e.to,t,min(f,e.cost)); if(d>0){ e.cost -= d; g[e.to][e.rev].cost += d; return d; } } return 0; } //start:s->to:t T max_flow(graph<T>&g,int s,int t){ T flow = 0; while(1){ vis.assign(g.n,0); T d = dfs(g,s,t,INF); if(d==0){ return flow; }else{ flow += d; } } return 0; } }; int main(){ cout << fixed << setprecision(15); int n; cin>>n; graph<int> g(n+2); int now = 0; rep(i,0,n){ int b,c; cin>>b>>c; if(b>c){ now += b; b -= c; g.addedge(i,n+1,b); }else{ now += c; c -= b; g.addedge(n,i,c); } } int m; cin>>m; int inf = (int)1e9; rep(i,0,m){ int a,b; cin>>a>>b; g.addedge(b,a,inf); } FordFulkerson<int> f; print(now-f.max_flow(g,n,n+1)); //system("pause"); return 0; }