TopCoder SRM 575 Div1 Hard TheTilesDivOne

Div2に続きDiv1のHardにチャレンジ。
「最大フローで解けるらしい？」との情報をもとにチャレンジ。
http://community.topcoder.com/stat?c=problem_statement&pm=12500

問題

Div2 Hardと同じ。
ただし高さHの最大値が4→47と増加。

解法

Div2の方法はO(W*2^H)なので、H=47では適用できない。
最大フローで解けるということで、最大フローの作り方を考えてみた。

最初はＬ字ブロックを１つ置くと、黒マス１つにつき白マス２つ消費するので、sourceから全黒マスに帯域２の辺を引き、そこから２つの白マスに帯域１の辺を引き、白マスからsinkに辺を引こうと思ったけど、こういう「１つの黒と２つの白を対応付ける」みたいなことはできないのね。

ここで、２つの白マスに注目すると、２つの白マスは片方がX座標が偶数、もう片方が奇数になる点に着目した。
そこで、以下の様にそれぞれ帯域1の辺を張ってみた。
source→X座標が偶数の白マス→そこに隣接する黒マス(黒マス消費前)→同黒マス(黒マス消費後)→隣接すX座標が奇数の白マス→sink
これだとsoruce→sinkに到達するのに２つの白マスに対応する点と、１つの黒マスに対応する辺を通過しなければならない。

後はMaxFlowを計算するだけ。
以前MinCostFlowのライブラリを作ったのに、なぜかまだMaxFlowのライブラリが無かったので蟻本を参考についでに作った。

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();}
	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) {
				if((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 TheTilesDivOne {
	public:
	int find(vector <string> board) {
		int x,y,W,H;
		MaxFlow m;
		m.init();
		H=board.size();
		W=board[0].size();
		
		FOR(y,H) FOR(x,W) {
			if(board[y][x]=='X') continue;
			if((x+y)%2==0) {
				//black
				m.add_edge(y*W+x,y*W+x+4900,1);
				if(x%2==0) {
					if(x>0) m.add_edge(y*W+x+4900,y*W+(x-1),1);
					if(x<W-1) m.add_edge(y*W+x+4900,y*W+(x+1),1);
				}
				else {
					if(y>0) m.add_edge(y*W+x+4900,(y-1)*W+x,1);
					if(y<H-1) m.add_edge(y*W+x+4900,(y+1)*W+x,1);
				}
			}
			else {
				if(x%2==0) {
					m.add_edge(9990,y*W+x,1);
					if(y>0) m.add_edge(y*W+x,(y-1)*W+x,1);
					if(y<H-1) m.add_edge(y*W+x,(y+1)*W+x,1);
					if(x>0) m.add_edge(y*W+x,y*W+(x-1),1);
					if(x<W-1) m.add_edge(y*W+x,y*W+(x+1),1);
				}
				else {
					m.add_edge(y*W+x,9991,1);
				}
			}
		}
		return m.maxflow(9990,9991);
		
	}
}

まとめ

若干のヒントありとはいえ、1000ptのD1Hを解いたのは初めてかも？
最大化問題ではDP・フロー・Bit Index Treeあたりを使うことが多いな。
うまくフローを使う最大化の方法を覚えよう。