AOJ 2313 Box Witch

問題

全ての辺の容量が1であるような無向グラフがあたえられる。
このグラフに辺の追加と削除のクエリがくる。
それぞれのクエリの後での、1番の頂点からn番の頂点への最大流の大きさを求めよ。

制約条件

N≦500
M≦20000
任意の２頂点間に張られる辺の本数は高々１本
削除、追加のクエリにおいて、グラフはきちんと削除、追加ができる状態になっている。

方針

毎回ナイーブに最大流を求めるとTLE.
増減分だけフローを流す。

あらかじめ、全てのクエリの分は容量0として辺を張っておく。
辺の追加のクエリは、容量を1増やして、追加のフローを求める。

辺の削除のクエリは蟻本のちゃんとしたやり方を忘れたので以下のようにやった。
今辺e(A, B)に流量1のフローが流れているとする。
AからBへの流量1の最大流を求める。見つかった場合、
e(A, B)のフローをそれに置き換えればいい。

見つからなかったとき、t→sに流量1のフローを流す。
その後で、AからBに流量1の最大流を流して、（必ず流れる）
e(A, B)のフローを消せばいい。

ソースコード

int n, e, q;
int m[1000], a[1000], b[1000];

int main(){
	cin >> n >> e >> q;
	map<pi, int> id;
	flowGraph g(n);
	rep(i, e){
		int f, t;
		cin >> f >> t;
		f--; t--;
		rep(it, 2){
			int j = g.add(f, t, 1);
			if(!id.count(mp(f, t))) id[mp(f, t)] = j;
			swap(f, t);
		}
	}
	rep(i, q){
		cin >> m[i] >> a[i] >> b[i];
		a[i]--; b[i]--;
		rep(it, 2){
			if(!id.count(mp(a[i], b[i]))){
				int j = g.add(a[i], b[i], 0);
				id[mp(a[i], b[i])] = j;
			}
			swap(a[i], b[i]);
		}
	}
	int ans = g.max_flow(0, n - 1);
	
	rep(i, q){
		if(m[i] == 1){
			g.G[a[i]][id[mp(a[i], b[i])]].cap++;
			g.G[b[i]][id[mp(b[i], a[i])]].cap++;
			ans += g.max_flow(0, n - 1);
		}
		else{
			int j = g.G[a[i]][id[mp(a[i], b[i])]].rev;
			if(g.G[b[i]][j].cap == 0){
				swap(a[i], b[i]);
				j = g.G[a[i]][id[mp(a[i], b[i])]].rev;
			}
			
			int t = g.max_flow(a[i], b[i], 1);
			if(!t){
				g.max_flow(n - 1, 0, 1);
				int u = g.max_flow(a[i], b[i], 1);
				assert(u);
				ans--;
			}
			g.G[a[i]][id[mp(a[i], b[i])]].cap = 0;
			g.G[b[i]][j].cap = 0;
			g.G[b[i]][id[mp(b[i], a[i])]].cap = 0;
			g.G[a[i]][g.G[b[i]][id[mp(b[i], a[i])]].rev].cap = 0;
		}
		cout << ans << endl;
	}
	return 0;
}