AOJ 2313 Box Witch
解法
ちゃんとフローがわかってるなら解ける問題.
まず辺の追加クエリは簡単で,単純に辺を増やすだけ.
問題は辺の削除クエリです.与えられた辺を $\{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; } }
感想
フローのいい練習になりそうな問題.