Chess Board (ZOJ Problem Set - 3548)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3548

問題

h*wの黒と白で塗られた盤面がある。これに対してa>=bという条件の下で図のようにn*mの白い正方形を書いていく。Helenはある長方形をt時間である色に塗ることができる。しかし目的の色と違う場合は、例えば白に塗りたい場所を黒に塗るなどはできない。最低何時間で色を塗り終えることが出来るか？
3<=h,w<=2000
1<=n,m<=200
0<=t<=1000

解法

a,bを固定してどの程度の時間で塗り終えることが出来るかを考える。
条件より白い部分に黒いピクセルが混じっている場合はその部分を白で塗らなければならない。白い部分と白い部分(もしくは端)の間の、黒で塗りたい部分に白いピクセルが混じっている場合はその列(行)を黒で塗る。
最後に黒の公差点の部分でまだ白いピクセルが残っている部分はXノードとYノードに分けた2部グラフのmincutで塗る時間の最小値を求めることができる。
ちなみに白いピクセルが混じっているかどうかはsumを前処理で求めておいてO(1)で計算すること。