AOJ 2313 Box Witch

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2313

解法

ちゃんとフローがわかってるなら解ける問題．
まず辺の追加クエリは簡単で，単純に辺を増やすだけ．
問題は辺の削除クエリです．与えられた辺を $\{a, b\}$ とします．
今流れてるフローで与えられた辺が使われていないなら，単純に削除します（これは辺のキャパシティ $cap[u][v]$ を持っておいて，$cap[a][b] \neq 1$ であるかで判定できます．どっちが 0 かで流れている向きもわかる．）
使われている場合，残余グラフ上で $a \rightarrow b$ のパスが残っているなら，$a \rightarrow b$ のフローを1ながして $\{a, b\}$ を消せば，整合性を損なうことなく流量を維持できます．
もし $a \rightarrow b$ のパスがない場合，一旦 $n \rightarrow 1$ へのフローを1流し直して，そのあと $a \rightarrow b$ のフローを流すと，自然にもともとの $a \rightarrow b$ のフローを打ち消すことが出来ます．
あとは辺を消してフローを流し直すだけで終わります．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using graph = vector<vector<int>>;

int dfs(graph& g, vector<bool>& visited, vector<vector<int>>& cap, int v, int t) {
    if(v == t) {
        return 1;
    }
    visited[v] = true;
    for(auto to : g[v]) {
        if(visited[to] || cap[v][to] == 0) {
            continue;
        }
        if(dfs(g, visited, cap, to, t) == 1) {
            cap[to][v]++;
            cap[v][to]--;
            return 1;
        }
    }
    return 0;
}

int max_flow(graph& g, vector<vector<int>>& cap, int s, int t, int cnt = 100000) {
    vector<bool> visited(g.size());
    int f = 0;
    while(cnt--) {
        fill(visited.begin(), visited.end(), false);
        if(dfs(g, visited, cap, s, t) == 1) {
            f++;
        } else {
            break;
        }
    }
    return f;
}

int main() {
    int N, E, Q;
    cin >> N >> E >> Q;
    graph g(N);
    vector<vector<int>> cap(N, vector<int>(N));
    auto add_edge = [&](int from, int to) {
        g[from].push_back(to);
        g[to].push_back(from);
        cap[from][to] = cap[to][from] = 1;
    };
    for(int i = 0; i < E; ++i) {
        int f, t;
        cin >> f >> t;
        f--; t--;
        add_edge(f, t);
    }

    int res = max_flow(g, cap, 0, N - 1);
    while(Q--) {
        int m, a, b;
        cin >> m >> a >> b;
        a--; b--;
        if(m == 1) {
            add_edge(a, b);
        } else {
            // used b -> a
            if(cap[a][b] == 2) {
                // doesn't exist circuit b -> a on residual graph
                if(max_flow(g, cap, b, a, 1) == 0) {
                    max_flow(g, cap, N - 1, 0, 1);
                    max_flow(g, cap, b, a, 1);
                    res--;
                }
            } else if(cap[b][a] == 2) {
                if(max_flow(g, cap, a, b, 1) == 0) {
                    max_flow(g, cap, N - 1, 0, 1);
                    max_flow(g, cap, a, b, 1);
                    res--;
                }
            }

            cap[a][b] = cap[b][a] = 0;
            g[a].erase(find(g[a].begin(), g[a].end(), b));
            g[b].erase(find(g[b].begin(), g[b].end(), a));
        }

        res += max_flow(g, cap, 0, N - 1);
        cout << res << endl;
    }
}

感想

フローのいい練習になりそうな問題．