CF1913E Matrix Problem 题解

蒟蒻君HJT · 2023-12-19 19:09:15 · 题解

先尝试判断无解：\displaystyle\sum A_i\neq \sum B_j 是必然无解的。但是这不充分。

仅仅判断是否有解不依赖给定的矩阵 a_{i,j}，如果我们从全 0 矩阵出发的话，会发现把 0 翻转成 1 的操作类似于二分图多重匹配：左部点 n 个表示行，右部点 m 个表示列，左右任意两点间存在一条待匹配边。(i_{left},j_{right}) 选入匹配，表示令 a_{i,j}\leftarrow 1。每个点的匹配次数的限制是恰好 A_i 或 B_j 次。问题转化成了匹配的可行性判断。

好，现在我们会判是否有解了，但是怎么求出最少的翻转次数呢？不妨先把所有 1 都翻转为 0，令基础答案 pans 为原本 1 的个数。之后每条待匹配边都带权，a_{i,j} 为 0 的话 (i_{left},j_{right}) 权值设为 1，表示要翻转 1 次；a_{i,j} 为 1 的话 (i_{left},j_{right}) 权值设为 -1，相当于翻回来。容易想到添加源汇点后，用最小费用最大流求解。

但这样有个问题：负环导致死循环。注意到我们最后选出的匹配边总数是确定的 \displaystyle\sum A_i，因此我们再令 pans \leftarrow pans-\displaystyle\sum A_i，并令匹配边的权值都加上 1 就行了。用 Dijkstra 增广的理论复杂度是 \Theta(n^2m^2(\log n+\log m))，实际跑不满。

for reference only.