AOJ-2313 : Box Witch

AOJ

問題概要

ノード数V(<500)、辺数E(<20000)の無向グラフが与えられる。辺の容量が1ずつ増減するクエリがQ(<1000)個くるので変化後の最大流を毎回答える問題。

解法

Introduction to Algorithmsとかにも載っている問題。増加のクエリに答えるのは簡単。減少のクエリに対しては、該当する辺を含む閉路があればそれを除去して、閉路が無ければそれを通るようにsinkからsourceへ流量1を押し戻す。その辺を通るようなのsinkからsourceへの押し戻しは、消したい辺がx->yのときx->sourceへ流すのとsink->yへ流すので分けてやったけど何か途中で流量保存則満たさない感じになって違和感があった。後で解説見たら何も考えずにsinkからsourceへ流量1流したらそのまま消えるかその辺を含む閉路ができるかのどちらかであることを使っていて賢かった。

acceptされたコード

計算量O(N*M+(M+Q)*Q)。

#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;

typedef int flow_t;

const int MAX_N = 500;
const int MAX_E = 20000;
const int MAX_Q = 1000;

struct edge{
	int tar;
	flow_t cap;
	bool on;
};

struct query{
	int cmd;
	int x, y;
};

int V, E, Q;
vector<edge> graph[MAX_N];
int id_table[MAX_N][MAX_N];
query qs[MAX_Q];

void add_edge(int x, int y, flow_t cap, bool on){
	id_table[x][y] = graph[x].size();
	id_table[y][x] = graph[y].size();
	graph[x].push_back((edge){y, cap, on});
	graph[y].push_back((edge){x, cap, on});
}

void init(){
	scanf("%d%d%d", &V, &E, &Q);
	memset(id_table, -1, sizeof(id_table));
	for(int i=0; i<E; i++){
		int x, y;
		scanf("%d%d", &x, &y);
		x--; y--;
		add_edge(x, y, 1, true);
	}

	for(int i=0; i<Q; i++){
		int c, x, y;
		scanf("%d%d%d", &c, &x, &y);
		x--; y--;
		qs[i] = (query){c, x, y};
		if(id_table[x][y] == -1){
			add_edge(x, y, 0, false);
		}
	}

}

bool visited[MAX_N];
int vis_time[MAX_N];

bool dfs(int v, int sink){
	if(v == sink){
		return true;
	}
	visited[v] = true;
	for(int i=0; i<(int)graph[v].size(); i++){
		edge& e = graph[v][i];
		if(e.on && e.cap > 0 && !visited[e.tar] && dfs(e.tar, sink)){
			e.cap--;
			graph[e.tar][id_table[e.tar][v]].cap++;
			return true;
		}
	}

	return false;
}

bool rem_dfs(int v){
	vis_time[v] = 2;
	for(int i=0; i<(int)graph[v].size(); i++){
		edge& e = graph[v][i];
		if(e.on && e.cap > 0){
			if(vis_time[e.tar] == 1 || (vis_time[e.tar] == 0 && rem_dfs(e.tar))){
				e.cap--;
				graph[e.tar][id_table[e.tar][v]].cap++;
				return true;
			}
		}
	}
	return false;
}

bool remove_cycle(int x, int y){
	memset(vis_time, 0, sizeof(vis_time));
	vis_time[y] = 1;
	return rem_dfs(x);
}

void solve(){
	const int source = 0, sink = V - 1;
	flow_t current = 0;

	for(;memset(visited, false, sizeof(visited)), dfs(source, sink); current++);

	for(int i=0; i<Q; i++){
		if(qs[i].cmd == 1){
			int x = qs[i].x, y = qs[i].y;
			graph[x][id_table[x][y]].on = true;
			graph[y][id_table[y][x]].on = true;
			graph[x][id_table[x][y]].cap = 1;
			graph[y][id_table[y][x]].cap = 1;
			memset(visited, false, sizeof(visited));
			if(dfs(source, sink)){
				current++;
			}
		}
		else{
			int x = qs[i].x, y = qs[i].y;
			if(graph[x][id_table[x][y]].cap != 1){
				// 現在はx -> yと流れているように一般化
				if(graph[x][id_table[x][y]].cap == 2){
					swap(x, y);
				}
				if(!remove_cycle(x, y)){
					graph[x][id_table[x][y]].on = false;
					graph[y][id_table[y][x]].on = false;
					memset(visited, false, sizeof(visited));
					dfs(x, source);
					memset(visited, false, sizeof(visited));
					dfs(sink, y);
					current--;
				}
			}
			graph[x][id_table[x][y]].on = false;
			graph[y][id_table[y][x]].on = false;
			graph[x][id_table[x][y]].cap = 0;
			graph[y][id_table[y][x]].cap = 0;
		}
		printf("%d\n", current);
	}
}

int main(){
	init();
	solve();

	return 0;
}