結果

問題 No.904 サメトロ
コンテスト
ユーザー nawawan
提出日時 2021-04-02 01:02:18
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 2,561 bytes
コンパイル時間 1,042 ms
コンパイル使用メモリ 85,668 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-12-21 08:57:40
合計ジャッジ時間 2,202 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;
template<typename T>
struct Dinic{
    struct edge{
        int to;
        T cap;
        int rev;
    };
    int V;
    T INF;
    vector<int> level, used;
    vector<vector<edge>> G;
    Dinic(int N): INF(numeric_limits<T>::max()), V(N), used(N), level(N), G(N){}
    void add(int u, int v, T c){
        edge e1 = {v, c, (int)G[v].size()};
        G[u].push_back(e1);
        edge e2 = {u, 0, (int)G[u].size() - 1};
        G[v].push_back(e2);
    }
    void bfs(int s){
        level.assign(V, -1);
        queue<int> q;
        q.push(s);
        level[s] = 0;
        while(!q.empty()){
            int v = q.front();
            q.pop();
            for(edge e: G[v]){
                if(e.cap > 0 && level[e.to] < 0){
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
        }
    }
    T dfs(int s, int t, T f){
        if(s == t) return f;
        for(int &i = used[s]; i < (int)G[s].size(); i++){
            edge &e = G[s][i];
            if(e.cap > 0 && level[e.to] > level[s]){
                T d = dfs(e.to, t, min(f, e.cap));
                if(d > 0){
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    T solve(int s, int t){
        T flow = 0;
        while(1){
            bfs(s);
            if(level[t] < 0) return flow;
            used.assign(V, 0);
            long long f;
            while((f = dfs(s, t, INF)) > 0) flow += f;
        }
    }
};
int main(){
    int N;
    cin >> N;
    Dinic<int> D(N * 2 + 2), D2((N - 1) * 2 + 2);
    D.add(N * 2, 0, D.INF);
    D.add(N, N * 2 + 1, D.INF);
    int sum = 0;
    int sumb = 0;
    for(int i = 0; i < N - 1; i++){
        int a, b;
        cin >> a >> b;
        sum += a;
        sumb += b;
        D.add(N * 2, i + 1, a);
        D.add(N + i + 1, N * 2 + 1, b);
        D2.add((N - 1) * 2, i, a);
        D2.add(i + N - 1, (N - 1) * 2 + 1, b);
    }
    for(int i = 0; i < N - 1; i++){
        for(int j = 0; j < N - 1; j++){
            if(i != j) D2.add(i, N - 1 + j, D2.INF);
        }
    }
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(i != j){
                D.add(i, N + j, D.INF);
            }
        }
    }
    int s = D2.solve(2 * (N - 1), 2 * (N - 1) + 1);
    int t = D.solve(2 * N, 2 * N + 1);
    cout << t - sum - (sumb - s) + 1 << endl;
}
0