TopCoder SRM 570 Div1 Hard CurvyonRails

問題

hxwの土地があって、それぞれのマスはfield[i][j]で表される。
filed[i][j]が'w'のところは荒野で、
'C'のところはCurviesがいるところ、
'.'のところは何もないところである。

'w'以外の全てのマスに、線路を引く。
線路はマスの４辺のうち、２つを接続する折れ線である。

線路は、両端が別の線路とつながっていなければならない。
が、線路が連結になっている必要はない。

線路は好きに曲げていいが、'C'のマスで曲げると1のコストがかかる。
条件を満たす線路の引き方のうち、最小のコストを求めよ。
線路が引けない場合は-1と答えよ。

制約条件

h,w≦50

方針

writerのsnukeさんのブログに解説がある。
http://snuke.hatenablog.com/entry/2013/02/13/225339
これの通り。

まずグリッドグラフなので２部グラフとして考えるのが自然。
２部グラフにすると、INとOUTを自然に作ることができる。

で、各マスについて、上下左右のうち２つを選ぶことができる。
曲がったときにコスト1を表現したいから、
上下方向の頂点と、左右方向の頂点に頂点を分裂させる。

で、上下と左右合わせて2つを選ぶようにするが、曲がるときにコスト1にしたい。
これは、上下の頂点と、左右の頂点に1ずつフローを流して、
両方上下または左右を使うときは、上下or左右のほうの流量が2になるので、
上下の頂点と左右の頂点をコスト1, 流量1の辺でつなげばよいことがわかる。

という感じで考えると思いつくのだろうか。
二部グラフにすると、INとOUTを自然に作れるというのが会得できてれば思いつきそうな気もする。

ソースコード

class CurvyonRails {
	public:
	int getmin(vector <string> field) {
		
		int h = field.size(), w = field[0].size();
		int s = h * w * 2, t = s + 1;
		costflowGraph<int> g(t + 1);
		
		int ca = 0, cb = 0;
		
		rep(i, h) rep(j, w) if(field[i][j] != 'w'){
			rep(d, 4){
				int y = i + dy[d], x = j + dx[d];
				if(y < 0 || x < 0 || y >= h || x >= w || field[y][x] == 'w') continue;
				
				if((i + j) % 2)
				g.add((i * w + j) * 2 + (d < 2), (y * w + x) * 2 + (d < 2), 1, 0);
			}
			if((i + j) % 2){
				ca++;
				rep(k, 2) g.add(s, (i * w + j) * 2 + k, 1, 0);
			}
			else{
				cb++;
				rep(k, 2) g.add((i * w + j) * 2 + k, t, 1, 0);
			}
			rep(k, 2)
			g.add((i * w + j) * 2 + k, (i * w + j) * 2 + 1 - k, 1, field[i][j] == 'C');
		}
		return ca == cb ? g.min_cost_flow(s, t, ca + cb) : -1;
	}
};