Algoogle

Algorithm for Programming Contest

AOJ 2313 Box Witch

Category: AOJ Tag: max-flow

Box Witch

問題概要


ソースからシンクまで最大流を流す.
辺の追加と削除のクエリが来るので,各操作後の最大流を答えよ.

解法


毎回1から最大流流していたら当然間に合わない.
差分だけ流すようにする.
クエリに来る辺は全部用意しておいて,まだ存在しない辺は容量を0にする.

  • 辺の追加のとき

その辺の容量を1にする.そのあと1だけフローを流す.

  • 辺の削除のとき

その辺の容量を0にする.
使われてないなら終わり.使われてるならその辺の両端の間にフローを流す.
流せたなら終わり.流せなかったらシンクから辺の端点,もう一方の端点からソースへ1だけフローを流す.
この際に,もともとの流れていた方向を考慮すること.

コード


(2313.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repi(i,0,n)

const int inf = 1e9;

struct max_flow {
    struct edge { int to, cap, rev; };
    int V;
    vector<vector<edge>> G;
    vector<int> itr, level;

    max_flow() {}
    max_flow(int V) : V(V) { G.assign(V,vector<edge>());}

    void add_edge(int from, int to, int cap) {
        G[from].push_back((edge) {to, cap, (int) G[to].size()});
        G[to].push_back((edge) {from, cap, (int) G[from].size()-1});
    }

    void bfs(int s) {
        level.assign(V,-1);
        queue<int> q;
        level[s] = 0; q.push(s);
        while (!q.empty()) {
            int v = q.front(); q.pop();
            for(auto &e: G[v]){
                if (e.cap > 0 and level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
        }
    }

    int dfs(int v, int t, int f) {
        if (v == t) return f;
        for (int& i = itr[v]; i < (int) G[v].size(); ++i) {
            edge& e = G[v][i];
            if (e.cap > 0 and level[v] < level[e.to]) {
                int 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;
    }

    int run(int s, int t, int lim = inf) {
        int ret = 0, f;
        while (bfs(s), level[t] >= 0 and lim) {
            itr.assign(V,0);
            while (lim and (f = dfs(s, t, lim)) > 0) {
                ret += f;
                if(lim != inf) lim -= f;
            }
        }
        return ret;
    }

    void cancel(int s, int t) {
        bfs(s);
        itr.assign(V,0);
        if(level[t] >= 0) dfs(s,t,1);
    }
};


int n, m, q, ex[512][512];
vector<tuple<int,int,int>> qs;
max_flow mf;

void solve() {
    int f = mf.run(0,n-1), a, u, v;
    for(auto &q: qs) {
        tie(a,u,v) = q;
        if(a == 1) {
            for(auto &e: mf.G[u]) {
                if(e.to == v) {
                    e.cap = mf.G[v][e.rev].cap = 1;
                    f += mf.run(0,n-1);
                    break;
                }
            }
        }
        else {
            for(auto &e: mf.G[u]) {
                if(e.to == v) {
                    int d = e.cap;
                    e.cap = mf.G[v][e.rev].cap = 0;
                    if(d == 1) break;
                    if(d == 2) {
                        if(mf.run(v,u,1)) break;
                        mf.run(n-1,u,1);
                        mf.run(v,0,1);
                    }
                    else {
                        if(mf.run(u,v,1)) break;
                        mf.run(n-1,v,1);
                        mf.run(u,0,1);
                    }
                    f--;
                    break;
                }
            }
        }
        cout << f << endl;
    }
}

void input() {
    cin >> n >> m >> q;
    mf = max_flow(n);
    int a, b, c;
    rep(i,m) {
        cin >> a >> b;
        a--; b--;
        mf.add_edge(a,b,1);
        ex[a][b] = ex[b][a] = 1;
    }
    rep(i,q) {
        cin >> a >> b >> c;
        b--; c--;
        qs.push_back(make_tuple(a,b,c));
        if(!ex[b][c]) {
            ex[b][c] = ex[c][b] = 1;
            mf.add_edge(b,c,0);
        }
    }
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cout << fixed << setprecision(12);
    input();
    solve();
    return 0;
}

Comments