結果
問題 | No.904 サメトロ |
ユーザー |
![]() |
提出日時 | 2019-10-11 23:06:36 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 1,904 bytes |
コンパイル時間 | 797 ms |
コンパイル使用メモリ | 69,684 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-25 09:17:26 |
合計ジャッジ時間 | 1,768 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <iostream>#include <stdio.h>#include <vector>#include <queue>#define llint long long#define inf 1e18using namespace std;struct edge{llint to, cap, rev;edge(llint a, llint b, llint c){to = a, cap = b, rev = c;}};llint n;llint a[40], b[40];vector<edge> G[80];int S, T;llint level[80], iter[80];void bfs(llint s){for(int i = 1; i <= T; i++) level[i] = inf;level[s] = 0;queue<int> Q;Q.push(s);while(Q.size()){int v = Q.front();Q.pop();for(int i = 0; i < G[v].size(); i++){int u = G[v][i].to;if(G[v][i].cap <= 0 || level[u] < inf) continue;level[u] = level[v] + 1;Q.push(u);}}}llint dfs(int v, llint f){if(v == T) return f;llint ret;for(int i = iter[v]; i < G[v].size(); i++){if(level[v] >= level[G[v][i].to] || G[v][i].cap <= 0) continue;ret = dfs(G[v][i].to, min(f, G[v][i].cap));if(ret > 0){G[v][i].cap -= ret;G[G[v][i].to][G[v][i].rev].cap += ret;return ret;}}return 0;}void add_edge(int s, int t, llint cap){G[s].push_back(edge(t, cap, G[t].size()));G[t].push_back(edge(s, 0, G[s].size()-1));}int main(void){ios::sync_with_stdio(0);cin.tie(0);cin >> n;for(int i = 2; i <= n; i++) cin >> a[i] >> b[i];llint asum = 0, bsum = 0;for(int i = n; i >= 2; i--) asum += a[i], bsum += b[i];if(asum > bsum){swap(asum, bsum);for(int i = 2; i <= n; i++) swap(a[i], b[i]);}S = 2*n+1, T = 2*n+2;for(int i = 2; i <= n; i++) add_edge(S, i, a[i]);for(int i = 2; i <= n; i++) add_edge(n+i, T, b[i]);for(int i = 2; i <= n; i++){for(int j = 2; j <= n; j++){if(i == j) continue;add_edge(i, n+j, inf);}}llint ans = 0, flow;while(1){bfs(S);if(level[T] >= inf) break;for(int i = 1; i <= T; i++) iter[i] = 0;while(1){flow = dfs(S, inf);if(flow <= 0) break;ans += flow;}}cout << ans + 1 << endl;return 0;}