TopCoder SRM422 Div1Hard

問題

グリッド状の土地があり、金鉱、銀鉱、ワークスペースがある。それ以外のマスには芝生か岩である。
何人かの労働者を雇って、金銀の採掘をさせたい。各労働者には1つずつの金鉱、銀鉱、ワークスペースが与えられる。これらは複数人の労働者で共有してはいけない。
ワークスペースから、金鉱、銀鉱までの距離は、それぞれK以下でないといけない。移動の際に通れるマスは芝生のマスのみである。
雇える労働者の最大数を求めよ。

解答

ワークスペースと、金鉱、銀鉱の間で、つなげるかどうかの表をまず作成する。
これは、BFSによって各ワークスペースからの距離を求めることでできる。
その後、[起点]->[金鉱]->[ワークスペース1]->[ワークスペース2]->[銀鉱]->[終点]の有向グラフを作成する。
[起点]->[金鉱]間はすべての金鉱に対して結ぶ。
[金鉱]->[ワークスペース1]、[ワークスペース2]->[銀鉱]間はつなげられる間のみで結ぶ。
ワークスペース1とワークスペース2は、同じワークスペースを複数人で共有しないための措置である。ワークスペース1のi番目とワークスペース2のi番目を結ぶ。
その上で起点->終点で最大流を求めるとそれが答えである。

コード

#include <vector>
#include <string>
#include <algorithm>
#include <queue>

class dinic
{
	/*
	for every edge (src, dest, cap, flow), it must have pair edge (dest, src, 0, -flow)
	*/

	struct edge
	{
		edge *next, *pair;
		int src, dest, cap, flow;
	};

	int v, e;
	edge *pool, **con; int top;

	int* level;

public:
	dinic(int _v, int _e)
	{
		v = _v; e = _e;
		pool = new edge[e];
		con = new edge*[v];
		for(int i=0;i<v;i++) con[i] = NULL;
		top = 0;
	}

	~dinic()
	{
		delete [] pool;
		delete [] con;
	}

	edge* _add_edge(int src, int dest, int cap)
	{
		edge* ed = &(pool[top++]);
		ed->src = src;
		ed->dest = dest;
		ed->cap = cap;
		ed->flow = 0;

		ed->next = con[src];
		con[src] = ed;

		return ed;
	}

	void add_pair(int src, int dest, int cap1, int cap2)
	{
		edge *e1 = _add_edge(src, dest, cap1);
		edge *e2 = _add_edge(dest, src, cap2);

		e1->pair = e2;
		e2->pair = e1;
	}

	int dfs(int s, int d, int cap)
	{
		if(s==d || cap==0) return cap;

		int w = 0;
		for(edge* ed = con[s]; ed != NULL; ed = ed->next)
			if(level[ed->dest] > level[s]){
				int f = dfs(ed->dest, d, std::min(cap - w, ed->cap - ed->flow));
				if(f > 0){
					ed->flow += f;
					ed->pair->flow -= f;
					w += f;
				}
			}

		return w;
	}

	long long max_flow(int s, int d)
	{
		level = new int[v];

		for(int i=0;i<e;i++) pool[i].flow = 0;

		long long ret = 0;

		for(bool update=true; update; ){
			update = false;

			//derminate distance
			std::fill(level, level+v, -1);
			level[s] = 0;
			std::queue<int> q;
			q.push(s);

			int ps;
			while(!q.empty()){
				ps = q.front(); q.pop();
				
				for(edge* ed = con[ps]; ed != NULL; ed = ed->next){
					if(ed->cap > ed->flow && level[ed->dest]==-1){
						level[ed->dest] = level[ps] + 1;
						q.push(ed->dest);
					}
				}
			}

			for(;;){
				int gain = dfs(s, d, 0x7FFFFFFF);
				if(gain==0) break;
				ret += gain;
				update = true;
			}
		}

		delete [] level;

		return ret;
	}
};

using namespace std;

int ax[4] = {-1, 0, 0, 1};
int ay[4] = {0, -1, 1, 0};

class WorkersOnPlane
{
	int fld[32][32], H, W;
	int gold, silver, work;
	bool conWG[900][900], conWS[900][900];
	
	void calc(int x, int y, int K)
	{
		for(int i=0;i<gold;i++) conWG[fld[x][y]][i] = false;
		for(int i=0;i<silver;i++) conWS[fld[x][y]][i] = false;
		
		int dist[32][32];
		for(int i=0;i<H;i++)
			for(int j=0;j<W;j++) dist[i][j] = 100000;
			
		queue<pair<int, int> > q;
		dist[x][y] = 0; q.push(make_pair(x, y));
		
		while(!q.empty()){
			pair<int, int> p = q.front(); q.pop();
			
			if(dist[p.first][p.second]>K) continue;
			if(fld[p.first][p.second]>=1000&&fld[p.first][p.second]<2000) conWG[fld[x][y]][fld[p.first][p.second]-1000] = true;
			if(fld[p.first][p.second]>=2000&&fld[p.first][p.second]<3000) conWS[fld[x][y]][fld[p.first][p.second]-2000] = true;

			if((p.first!=x||p.second!=y) && fld[p.first][p.second]!=-1) continue;
			for(int i=0;i<4;i++) if(dist[p.first+ax[i]][p.second+ay[i]] > dist[p.first][p.second]+1){
				dist[p.first+ax[i]][p.second+ay[i]] = dist[p.first][p.second]+1;
				q.push(make_pair(p.first+ax[i], p.second+ay[i]));
			}
		}
	}
	
public:
	int howMany(vector<string> field, int K)
	{
		H = field.size()+2; W = field[0].size()+2;
		for(int i=0;i<H;i++){
			for(int j=0;j<W;j++) fld[i][j] = -2;
		}
		gold = silver = work = 0;
		for(int i=0;i<H-2;i++){
			for(int j=0;j<W-2;j++){
				if(field[i][j]=='.') fld[i+1][j+1] = -1;
				if(field[i][j]=='X') fld[i+1][j+1] = -2;
				if(field[i][j]=='W') fld[i+1][j+1] = work++;
				if(field[i][j]=='G') fld[i+1][j+1] = 1000 + gold++;
				if(field[i][j]=='S') fld[i+1][j+1] = 2000 + silver++;
			}
		}
		
		for(int i=0;i<H;i++) for(int j=0;j<W;j++) if(fld[i][j]>=0&&fld[i][j]<1000) calc(i, j, K);
		
		dinic dn(2000, 200000);
		
		for(int i=0;i<gold;i++) dn.add_pair(0, i+2, 1, 0);
		for(int i=0;i<silver;i++) dn.add_pair(2+gold+2*work+i, 1, 1, 0);
		for(int i=0;i<work;i++) dn.add_pair(2+gold+i, 2+gold+work+i, 1, 0);
		for(int i=0;i<work;i++){
			for(int j=0;j<gold;j++) if(conWG[i][j]){
				dn.add_pair(j+2, 2+gold+i, 1, 0);
			}
			for(int j=0;j<silver;j++) if(conWS[i][j]){
				dn.add_pair(2+gold+work+i, 2+gold+2*work+j, 1, 0);
			}
		}
		
		return dn.max_flow(0, 1);
	}
};