ABC164 F - I hate Matrix Construction
フロー解の解説です
問題
日本語なので省略。
https://atcoder.jp/contests/abc164/tasks/abc164_f
解法
まず、(行/列)ごとの制約はビットごとの論理(積/和)なので、ビットごとに独立に答えを求めればいいです。(以降、説明の都合のため、$$a_{i,j}, U_i, V_i$$ は0か1であるとします)
問題を扱いやすくするために、論理(積/和)の制約をその(行/列)にある $$1$$ の数の制約に言い換えます。
すると、各行ごとの1の数は、以下を満たしていなければならないことになります。(列の時も同様)
- $$S_i = 0, U_i = 0$$ のとき、$$0$$ 個以上 $$N-1$$ 個以下
- $$S_i = 0, U_i = 1$$ のとき、ちょうど $$N$$ 個
- $$S_i = 1, U_i = 0$$ のとき、ちょうど $$0$$ 個
- $$S_i = 1, U_i = 1$$ のとき、1個以上 $$N$$ 個以下
これは、行と列を頂点、マスを「行から列に張った辺」に置き換えることで、次のようなグラフの最大流問題に帰着できます。
$$S$$ から $$T$$ にフローを流すことにすると、次のように元の行列と対応します。
- $$S$$ から $$i$$ 行目への辺には、$$i$$ 行目の $$1$$ の数の和だけ流れる
- $$i$$ 行目から $$j$$ 列目への辺には、$$a_{i, j}$$ が $$1$$ なら流量1だけ流れ、 $$0$$ なら流れない
- $$j$$ 列目から $$T$$ への辺には、$$j$$ 列目の $$1$$ の数の和だけ流れる
これを最大流で解くときには、真ん中の辺は単に流量 $$1$$ とすればよいです。
行と列の制約は少し厄介で、$$x$$以上$$y$$以下流さなければいけないので、最小流量制限付き最大流となります。これは、この記事にあるテクニックを使えばいいです。(説明丸投げ)
最大流を求めるのに Dinic 法を使うと、$$N+4$$ 頂点 $$N^{2} + \Theta (N)$$ 辺なので $$ O(N^{4}) $$ になって間に合わないように思えますが、グラフの形状の関係か、実際にはかなり早いです。
復元は、フローを流し切った後に流れているかどうかを確認すればよいです。これを $$64$$ 回繰り返せば答えを求めることができます。
