Binary Matrix (UVa Live Archive Asia Dhaka 2011)
問題
0,1で構成されるm*n行列がある。隣り合う要素同士をswapすることによって各行、各列にある1の個数を同じにしたい。swapの最小回数を求めよ。
2<=n,m<=1,000
解法
行、列は分けて処理して良い。この2つを分けると結局、隣り合う数値を横に1つずつずらせるという条件の下で全ての要素の値を同じにする問題になる。これは割り当て問題なので最小費用流を用いれば解ける。
また解説によると中央値を使うことにより高速に計算する手法もあるらしい。
