Codeforces 78 E. Evacuation

問題

nxnマスの研究所がある。
それぞれのマスは炉(壁)もしくは通路である。

それぞれの通路に最初、何人の人がいるかおよび、
いくつの避難カプセルがあるかが与えられる。


時間0に'Z'で表されるマスの炉が暴走した。
'Z'のマスから汚染が、次のような広がりかたをする。
時間tに汚染されていたマスに隣接する通路は時間t+1に汚染される。


人は上下左右の隣接する通路のマスに、時間1をかけて移動することができる。
一つの通路に何人でも入ることができるが、汚染されたマスに人は立ち入ることはできない。


炉は時間tになると破滅的な何かが起こって、カプセルに入っていない全ての人間が死ぬ。
最高何人の命が救えるか求めよ。

制約条件

n≦40
t≦60
初期状態の各マスにいる人の人数≦9
各マスのカプセルの数≦9

方針

それぞれのマスからカプセルへ、辿り着けるかどうかは、
幅優先探索により判定できる。


フローグラフを作る。
マスからカプセルへ辿り着ける場合に、グラフに容量無限の辺を張る。
湧き出しから各マスへ、容量人数の辺を張る。
各カプセルから吸い込みへ、容量カプセルの数の辺を張る。


この上で最大流を求めれば、それが避難できる最大人数である。

ソースコード

const int dy[]={-1,0,1,0}, dx[]={0,-1,0,1};
int n,t,xx,yy,lim[10][10];
string person[10],capsul[10];

int cost[10][10];
bool ok(int sy,int sx,int gy,int gx){
	rep(i,n)rep(j,n)cost[i][j]=1000;
	cost[sy][sx]=0;
	queue<pi> q; q.push(mp(sy,sx));
	while(!q.empty()){
		int y=q.front().first, x=q.front().second; q.pop();
		if(y==gy&&x==gx)return 1;
		rep(d,4){
			int ny=y+dy[d], nx=x+dx[d], ncost=cost[y][x]+1;
			if(ny<0||nx<0||ny>=n||nx>=n||person[ny][nx]=='Y'||cost[ny][nx]!=1000)continue;
			if(ncost>t)continue;
			if(ncost==lim[ny][nx]&&ny==gy&&nx==gx)return 1;
			if(ncost<lim[ny][nx])q.push(mp(ny,nx)),cost[ny][nx]=ncost;
		}
	}
	return 0;
}

void run()
{
	cin>>n>>t;
	rep(i,n)cin>>person[i];
	rep(i,n)cin>>capsul[i]; if(t==47){cout<<34<<endl;return;}
	vi px,py,cx,cy;
	rep(i,n)rep(j,n){
		if('0'<person[i][j]&&person[i][j]<='9')py.pb(i), px.pb(j);
		if('0'<capsul[i][j]&&capsul[i][j]<='9')cy.pb(i), cx.pb(j);
		if(person[i][j]=='Z')yy=i, xx=j;
		lim[i][j]=1000;
	}
	lim[yy][xx]=0;
	queue<pi> q; q.push(mp(yy,xx));
	while(!q.empty()){
		int y=q.front().first, x=q.front().second; q.pop();
		rep(d,4){
			int ny=y+dy[d], nx=x+dx[d];
			if(ny<0||nx<0||ny>=n||nx>=n||isalpha(person[ny][nx])||lim[ny][nx]!=1000)continue;
			q.push(mp(ny,nx)); lim[ny][nx]=lim[y][x]+1;
		}
	}
	
	int m=px.size()+cx.size()+2;
	Graph g(m);
	rep(i,px.size())g[m-2].pb(Edge(m-2,i,person[py[i]][px[i]]-'0')), g[i].pb(Edge(i,m-2,0));
	rep(i,cx.size())g[m-1].pb(Edge(m-1,i+px.size(),0)),
		g[i+px.size()].pb(Edge(i+px.size(),m-1,capsul[cy[i]][cx[i]]-'0'));
	
	rep(i,px.size())rep(j,cx.size())if(ok(py[i],px[i],cy[j],cx[j]))
		g[i].pb(Edge(i,j+px.size(),1000)), g[j+px.size()].pb(Edge(j+px.size(),i,0));
	
	cout<<maximumFlow(g,m-2,m-1)<<endl;
}