solution

答えは単に与えられた有向グラフの最大流。 辺の削除が計算量的に問題となるが、残余グラフ上を逆向きに流して容量を回復させればよい。 Ford-Fulkerson法で$O(N^2 + QN)$。

$a - b$間を削除したいとき:

  • $a \to b$にも$a \gets b$にも流れるならそのままでよい
  • $a \to b$に流れるが$a \gets b$に流れないなら$a, b$をswapして次の場合に帰着
  • $a \to b$に流れないが$a \gets b$に流れる場合
    • $a = \mathrm{src}, \; b = \mathrm{dst}$なら単に$\mathrm{dst} \to \mathrm{src}$に$1$流して最大流を$1$減らす
    • そうでないなら、$\mathrm{dst} \to \mathrm{src}$に容量$1$加えて$b \to a$で$1$流す (この仮定では必ず流せる)。 $\mathrm{dst} \to \mathrm{src}$の容量が減ってるかで場合分けして適当に

implementation

#include <cstdio>
#include <vector>
#include <array>
#include <limits>
#include <functional>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }

template <size_t N>
vector<int> augmenting_path(int src, int dst, array<array<int, N>, N> const & g) {
    array<bool, N> used = {};
    vector<int> acc;
    function<bool (int)> dfs = [&](int i) {
        acc.push_back(i);
        if (i == dst) return true;
        used[i] = true;
        repeat (j, N) if (not used[j] and g[i][j] >= 1) {
            if (dfs(j)) {
                return true;
            }
        }
        acc.pop_back();
        return false;
    };
    dfs(src);
    return acc;
}

template <size_t N>
int maximum_flow(int src, int dst, array<array<int, N>, N> & g) {
    int acc = 0;
    while (true) {
        auto path = augmenting_path(src, dst, g);
        if (path.empty()) break;
        int l = path.size();
        int delta = numeric_limits<int>::max();
        repeat (i, l - 1) setmin(delta, g[path[i]][path[i + 1]]);
        repeat (i, l - 1) {
            g[path[i]][path[i + 1]] -= delta;
            g[path[i + 1]][path[i]] += delta;
        }
        acc += delta;
    }
    return acc;
}

template <size_t N>
int unwind(int a, int b, int src, int dst, array<array<int, N>, N> & g) {
    if (g[a][b] == 0 and g[b][a] == 0) {
        assert (false);
    } else if (g[b][a] == 0) {
        return unwind(b, a, src, dst, g);
    } else if (g[a][b] == 0) {
        if (a == src and b == dst) {
            auto path = augmenting_path(dst, src, g);
            int l = path.size();
            assert (l >= 1);
            repeat (i, l - 1) {
                g[path[i]][path[i + 1]] -= 1;
                g[path[i + 1]][path[i]] += 1;
            }
            return 1;
        } else {
            assert (g[src][dst] == 0);
            g[src][dst] += 1;
            auto path = augmenting_path(a, b, g);
            int l = path.size();
            assert (l >= 1);
            repeat (i, l - 1) {
                g[path[i]][path[i + 1]] -= 1;
                g[path[i + 1]][path[i]] += 1;
            }
            g[a][b] += 1;
            g[b][a] -= 1;
            if (g[src][dst] == 0) {
                g[dst][src] -= 1;
                return 1;
            } else {
                g[src][dst] -= 1;
                return 0;
            }
        }
    } else {
        return 0;
    }
}

constexpr int max_n = 500;
array<array<int, max_n>, max_n> g;
int main() {
    int n, edges, queries; scanf("%d%d%d", &n, &edges, &queries);
    assert (n <= max_n);
    repeat (i, edges) {
        int from, to; scanf("%d%d", &from, &to); -- from; -- to;
        g[from][to] += 1;
        g[to][from] += 1;
    }
    const int src = 0;
    const int dst = n - 1;
    int flow = maximum_flow(src, dst, g);
    while (queries --) {
        int modify, a, b; scanf("%d%d%d", &modify, &a, &b); -- a; -- b;
        if (modify == 1) { // connect
            g[a][b] += 1;
            g[b][a] += 1;
            flow += maximum_flow(src, dst, g);
        } else if (modify == 2) { // disconnect
            assert (g[a][b] + g[b][a] == 2);
            flow -= unwind(a, b, src, dst, g);
            g[a][b] -= 1;
            g[b][a] -= 1;
            assert (g[a][b] >= 0);
            assert (g[b][a] >= 0);
            flow += maximum_flow(src, dst, g);
        } else {
            assert (false);
        }
        printf("%d\n", flow);
    }
    return 0;
}