UVa-563, Live Archive-5584 : Crimewave

問題概要

H*W(H,W<50)のグリッド線があり、いくつかの格子点上はマークされている。マークされている点からグリッドの線をたどってグリッドの外側まで向かいたい。ただし軌跡が交わってはならない。すべてのマークされている点を逃すことができるかどうか判定する問題。

解法

頂点に容量1を持たせた最大流を流せば良い。

acceptされたコード

計算量O((H*W)^3)くらい？実際は十分速い。

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

const int MAX_W = 50;
const int MAX_V = 2*MAX_W*MAX_W + 2;
const int INF = 1<<29;

int read_int(){
	int x;
	scanf("%d", &x);
	return x;
}

void init(){
	H = read_int();
	W = read_int();
	N = read_int();

	source = 2*H*W;
	sink = source + 1;
	V = sink + 1;

	for(int i=0; i<V; i++){
		G[i].clear();
	}

	for(int i=0; i<H; i++){
		for(int j=0; j<W; j++){
			add_edge(2*(i*W+j), 2*(i*W+j)+1, 1);
		}
	}

	const int dy[] = {0, 0, 1, -1}, dx[] = {1, -1, 0, 0};
	for(int i=0; i<H; i++){
		for(int j=0; j<W; j++){
			for(int k=0; k<4; k++){
				int y = i + dy[k], x = j + dx[k];
				if(0<=y && y<H && 0<=x && x<W){
					add_edge(2*(i*W+j)+1, 2*(y*W+x), 1);
				}
			}
		}
	}

	for(int k=0; k<N; k++){
		int y = read_int() - 1, x = read_int() - 1;
		add_edge(source, 2*(y*W+x), 1);
	}

	for(int i=0; i<H; i++){
		for(int j=0; j<W; j++)if(i==0 || j==0 || i==H-1 || j==W-1){
			add_edge(2*(i*W+j)+1, sink, 1);
		}
	}
}

int main(){
	for(int T = read_int(); T--; ){
		init();
		puts(max_flow(source, sink) == N ? "possible" : "not possible");
	}

	return 0;
}