TopCoder SRM 594 Div1 Medium FoxAndGo3

本番は「これフローなんだろうけど、うまいグラフに持ち込めないな…」と迷った問題。
結局本番は解けなかった。
http://community.topcoder.com/stat?c=problem_statement&pm=12808

問題

正方形の碁盤目上に、いくつか白黒石および空白マスがある。
初期状態で白石同士は隣接せず、また白石は1つ以上の空白マスに隣接している。

ここにいくつか黒石を足していく。
空白マスに隣接しない白石は取り除くことができる。
最適な黒石配置をした場合に、空白マス数を最大化せよ。

解法

白石を1個とりのぞけば空白マスを1個作れるが、そのために黒石を2個以上追加すると損である。
よって白石1個に対し空白マス1個以下に黒石を置いて取り除けるようにしたい。

白石と空白マスで二部グラフを作り、最大安定集合を作ればそれが答えになる。
二部グラフの最大安定集合の数なので、両マスの合計マス数から、二部グラフの最大マッチング数＝最大フローを引いたものが答え。

class MaxFlow {
public:
	struct edge { int to, capacity, reve;};
	static const int MV = 10000;
	vector<edge> E[MV];
	int vis[MV];
	
	void init() { for(int i=0;i<MV;i++) E[i].clear();}
	MaxFlow() {init();}
	void add_edge(int x,int y, int cap) {
		E[x].push_back((edge){y,cap,E[y].size()});
		E[y].push_back((edge){x,0, E[x].size()-1}); /* rev edge */
	}
	
	int dfs(int from,int to,int cf) {
		int i,tf;
		if(from==to) return cf;
		vis[from]=1;
		FOR(i,E[from].size()) {
			edge& e=E[from][i];
			if(vis[e.to]==0 && e.capacity>0 && (tf = dfs(e.to,to,min(cf,e.capacity)))>0) {
				e.capacity -= tf;
				E[e.to][e.reve].capacity += tf;
				return tf;
			}
		}
		return 0;
	}
	
	int maxflow(int from, int to) {
		int fl=0,tf;
		while(1) {
			ZERO(vis);
			if((tf = dfs(from,to,1<<29))==0) return fl;
			fl+=tf;
		}
	}
};

class FoxAndGo3 {
	public:
	int N;
	vector <string> B;
	
	int maxEmptyCells(vector <string> board) {
		B=board;
		N=B.size();
		
		MaxFlow mf;
		int x,y,i,tx,ty,b=0,e=0;
		int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
		FOR(x,N) FOR(y,N) {
			if(B[x][y]=='o') {
				b++;
				mf.add_edge(0,1+x*50+y,1);
				FOR(i,4) {
					tx=x+dx[i];ty=y+dy[i];
					if(tx<0 || ty<0 || tx>=N || ty>=N) continue;
					if(B[tx][ty]=='.') mf.add_edge(1+x*50+y,1+tx*50+ty,1);
				}
			}
			else if(B[x][y]=='.') {
				e++;
				mf.add_edge(1+x*50+y,3000,1);
			}
		}
		return b+e-mf.maxflow(0,3000);
	}
};

まとめ

最大フローを二部マッチングや最大独立集合などを結びつけるのが苦手。
蟻本の二部グラフの項目をもう少し読むか。