AOJ 2313: Box Witch

面倒そう面倒そうと言って毎回逃げていたのでそろそろ仕方なく埋めることにしました。
フローの辺たちを上手くDFSでいじるだけ。練習にはなる。

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int D_MAX_V=1100;
const int D_v_size=1100;
struct D_wolf{
	int t,c,r;
	D_wolf(){t=c=r=0;}
	D_wolf(int t1,int c1,int r1){
		t=t1;c=c1;r=r1;
	}
};
vector<D_wolf>D_G[D_MAX_V];
int D_level[D_MAX_V];
int D_iter[D_MAX_V];

void add_edge(int from,int to,int cap){
	D_G[from].push_back(D_wolf(to,cap,D_G[to].size()));
	D_G[to].push_back(D_wolf(from,cap,D_G[from].size()-1));
}
void D_bfs(int s){
	for(int i=0;i<D_v_size;i++)D_level[i]=-1;
	queue<int> Q;
	D_level[s]=0;
	Q.push(s);
	while(Q.size()){
		int v=Q.front();
		Q.pop();
		for(int i=0;i<D_G[v].size();i++){
			if(D_G[v][i].c>0&&D_level[D_G[v][i].t]<0){
				D_level[D_G[v][i].t]=D_level[v]+1;
				Q.push(D_G[v][i].t);
			}
		}
	}
}
int D_dfs(int v,int t,int f){
	if(v==t)return f;
	for(;D_iter[v]<D_G[v].size();D_iter[v]++){
		int i=D_iter[v];
		if(D_G[v][i].c>0&&D_level[v]<D_level[D_G[v][i].t]){
			int d=D_dfs(D_G[v][i].t,t,min(f,D_G[v][i].c));
			if(d>0){
				D_G[v][i].c-=d;
				D_G[D_G[v][i].t][D_G[v][i].r].c+=d;
				return d;
			}
		}
	}
	return 0;
}
int max_flow(int s,int t){
	int flow=0;
	for(;;){
		D_bfs(s);
		if(D_level[t]<0)return flow;
		for(int i=0;i<D_v_size;i++)D_iter[i]=0;
		int f;
		while((f=D_dfs(s,t,99999999))>0){flow+=f;}
	}
	return 0;
}
int v[510];
void init(){
	for(int i=0;i<510;i++)v[i]=0;
}
int dfs(int a,int b){
	v[a]=1;
	if(a==b)return 1;
	for(int i=0;i<D_G[a].size();i++){
		if(!v[D_G[a][i].t]&&D_G[a][i].c){
			int res=dfs(D_G[a][i].t,b);
			if(res){
				D_G[a][i].c--;
				D_G[D_G[a][i].t][D_G[a][i].r].c++;
				return 1;
			}
		}
	}
	return 0;
}
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<b;i++){
		int p,q;
		scanf("%d%d",&p,&q);p--;q--;
		add_edge(p,q,1);
	}
	int ret=max_flow(0,a-1);
	for(int i=0;i<c;i++){
		int p,q,r;
		scanf("%d%d%d",&r,&p,&q);p--;q--;
		if(r==1){
			bool ok=false;
			for(int j=0;j<D_G[p].size();j++){
				if(D_G[p][j].t==q){
					ok=true;
					D_G[p][j].c=1;
					D_G[q][D_G[p][j].r].c=1;
				}
			}
			if(!ok)add_edge(p,q,1);
			ret+=max_flow(0,a-1);
			printf("%d\n",ret);
		}else{
			for(int j=0;j<D_G[p].size();j++){
				if(D_G[p][j].t==q){
					if(D_G[p][j].c==1){
						D_G[p][j].c=D_G[q][D_G[p][j].r].c=0;
						break;
					}else if(D_G[p][j].c==0){
						D_G[p][j].c=D_G[q][D_G[p][j].r].c=0;
						init();
						int tmp=dfs(p,q);
						if(!tmp){
							ret--;
							init();
							dfs(a-1,q);
							init();
							dfs(p,0);
						}
					}else{
						D_G[p][j].c=D_G[q][D_G[p][j].r].c=0;
						init();
						int tmp=dfs(q,p);
						if(!tmp){
							ret--;
							init();
							dfs(a-1,p);
							init();
							dfs(q,0);
						}
					}
				}
			}
			printf("%d\n",ret);
		}
	}
}