AOJ 2313 - Box Witch

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

解法

まず初期状態のネットワークで最大流とそのときのフローを求める．

接続クエリがきたときは，そこの容量を1にして augment path を探し，見つかったらフローを更新して最大流を1増やす．

切断クエリがきたとき，そこにフローが流れていなければ単に容量を0にするだけ． そうでないときは，最大流を1減らして，そこに流れていた1のフローを BFS して打ち消す． その後，augment path を探して，見つかったらフローを更新して最大流を1増やす(元に戻す)．

  1 #include <iostream>
  2 #include <vector>
  3 #include <queue>
  4 using namespace std;
  5 
  6 bool augment(vector<vector<int> >& flow, const vector<vector<int> >& capacity, int s, int g)
  7 {
  8   int size = capacity.size();
  9   queue<int> q;
 10   vector<int> prev(size, -1);
 11   prev[s] = s;
 12   q.push(s);
 13   while (!q.empty()) {
 14     int n = q.front();
 15     q.pop();
 16     for (int i = 0; i < size; i++) {
 17       if (capacity[n][i] - flow[n][i] <= 0) continue;
 18       if (prev[i] != -1) continue;
 19       prev[i] = n;
 20       q.push(i);
 21       if (i == g) goto endloop;
 22     }
 23   }
 24 endloop:
 25   if (prev[g] == -1) return false;
 26   for (int i = g; prev[i] != i; i = prev[i]) {
 27     ++flow[prev[i]][i];
 28     --flow[i][prev[i]];
 29   }
 30   return true;
 31 }
 32 
 33 pair<int, vector<vector<int> > >
 34 maxflow(const vector<vector<int> >& capacity, int s, int g) {
 35   int size = capacity.size();
 36   vector<vector<int> > flow(size, vector<int>(size, 0));
 37   int ans = 0;
 38   while (augment(flow, capacity, s, g)) {
 39     ++ans;
 40   }
 41   return make_pair(ans, flow);
 42 }
 43 
 44 void bfs(vector<vector<int> >& flow, int start, int goal)
 45 {
 46   const int N = flow.size();
 47   queue<int> q;
 48   vector<int> prev(N, -1);
 49   q.push(start);
 50   prev[start] = start;
 51   while (!q.empty()) {
 52     int n = q.front();
 53     q.pop();
 54     if (n == goal) {
 55       while (prev[n] != n) {
 56         flow[prev[n]][n] = flow[n][prev[n]] = 0;
 57         n = prev[n];
 58       }
 59       return;
 60     }
 61     for (int i = 0; i < N; i++) {
 62       if (flow[n][i] > 0 && prev[i] == -1) {
 63         prev[i] = n;
 64         q.push(i);
 65       }
 66     }
 67   }
 68 }
 69 
 70 int main()
 71 {
 72   int N, E, Q;
 73   cin >> N >> E >> Q;
 74   vector<vector<int> > capacity(N, vector<int>(N, 0));
 75   for (int i = 0; i < E; i++) {
 76     int f, t;
 77     cin >> f >> t;
 78     --f;    --t;
 79     capacity[f][t] = capacity[t][f] = 1;
 80   }
 81 
 82   pair<int, vector<vector<int> > > r = maxflow(capacity, 0, N-1);
 83   int maxf = r.first;
 84   vector<vector<int> > flow = r.second;
 85   while (Q-- > 0) {
 86     int m, a, b;
 87     cin >> m >> a >> b;
 88     --a;    --b;
 89     if (m == 1) {
 90       capacity[a][b] = capacity[b][a] = 1;
 91     } else {
 92       capacity[a][b] = capacity[b][a] = 0;
 93       if (flow[a][b] != 0) {
 94         --maxf;
 95         if (flow[a][b] < 0) {
 96           swap(a, b);
 97         }
 98         flow[a][b] = flow[b][a] = 0;
 99         bfs(flow, 0, a);
100         bfs(flow, b, N-1);
101       }
102     }
103     if (augment(flow, capacity, 0, N-1)) {
104       ++maxf;
105     }
106 
107     cout << maxf << endl;
108   }
109   return 0;
110 }