Google Code Jam 2014 Round 2 : C. Don't Break The Nile

本番はSmallしか解けなかった。
https://code.google.com/codejam/contest/3014486/dashboard#s=p2

問題

南北に流れる川があり、W*Hの2次元グリッドの形で表現される。
川にはB個の長方形の島があり、そこは水が流れない。

各セルには容量１の水を蓄えることができる。
また、毎秒各セルの水は隣接するセルに流れることができる。
当然ながら、各セルに2以上水がたまることがない。

一番南の(島ではない)セルにはグリッド外から毎秒１の水が流れ込むことができる。
また、一番北の(島ではない)セルにはグリッド外に毎秒１の水を流すことができる。
安定状態で毎秒どの位の水が流れるか。

解法

smallではW*Hが50000以下なので、各セルを頂点とみなしたグラフを作り最大フロー問題を解けばよい。
hardではW,Hが非常に大きく、各セルを頂点とみなすグラフは巨大すぎて最大フローを時間内に求められない。

ここで、自力では解けなかったのでコード量が短かったfanhqme氏の回答を参考に解いてみた。
最大フロー最小カット定理より、最大フローを直接求めるのではなく、最小フローを求めればよい。
各島について、「その島の左側を流れる最大カットと右側を流れる空間（カット）の和」を求めてその最小値が答えとなる。

以下のコードでは島の右側は川端Wまでの間の太さの分だけ流すことができるとしている。
島の左側については、「その左側にある島と間の空間の太さの分」だけ流すことができる。
この隣接する島との距離を用いて、Warshall-Floydの要領で左側の空間を最小化すればよい。

左側の空間を最小化するのはいいとして、なぜ右側は無視してよいか？と気になるかもしれないが、最後「左側と右側の空間の和の最小値」を求める際、結果的に右側の空間が小さい島の時に和が最小となる。

以下のコードでは、島間の空間(D[x][y])を用いて左側の空間(DS[x])を最小化している。
O(N^3)なのでN=1000ではちょっと重いが、Core-i5でも1秒程度で終わる。

int W,H,B;
int X0[1001],Y0[1001],X1[1001],Y1[1001];
int DS[1001];
int D[1001][1001];

void solve(int _loop) {
	int f,i,j,k,l,x,y,x0,y0,x1,y1;
	
	cin>>W>>H>>B;
	
	FOR(i,B) cin>>X0[i]>>Y0[i]>>X1[i]>>Y1[i];
	FOR(i,B) DS[i]=X0[i];
	FOR(x,B) FOR(y,B) {
		D[x][y]=max(max(X0[x]-X1[y]-1,X0[y]-X1[x]-1),0);
		D[x][y]=max(max(Y0[x]-Y1[y]-1,Y0[y]-Y1[x]-1),D[x][y]);
	}
	
	int ret=W;
	FOR(i,B) FOR(x,B) FOR(y,B) DS[x]=min(DS[x],DS[y]+D[x][y]);
	FOR(i,B) ret=min(ret,DS[i]+W-(X1[i]+1));
	
	_P("Case #%d: %d\n",_loop,ret);
}

まとめ

smallを最大フローで解いたときよりもコードが小さくなった…。