场上疯狂想求任意解+改动解至最优。。想不下去的时候一定要再读一遍题跳出来啊。
限制每一行每一列的 \(1\) 的个数，这很匹配啊！！
考虑网络流，左侧 \(n\) 个节点连流量 \(a_i\)，右侧 \(m\) 个节点连流量 \(b_i\)。
对于原矩阵中为 \(0\) 的项 \((i,j)\)，若新矩阵中为 \(0\) 则流量为 \(0\)、费用为 \(0\)，若为 \(1\) 则流量为 \(1\)、费用为 \(1\)，故可以从 \(a_i\) 向 \(b_j\) 连边权为 \(1\)、费用为 \(1\) 的边；对于原矩阵中为 \(1\) 的项 \((i,j)\)，若新矩阵中为 \(0\) 则流量为 \(0\)、费用为 \(1\)，若为 \(1\) 则流量为 \(1\)、费用为 \(0\)，故可以默认花费一点费用，从 \(a_i\) 向 \(b_j\) 连边权为 \(1\)、费用为 \(-1\) 的边。由于所有环一定包含终点，故负权边不会造成影响。
之后跑 dinic 即可。
标签：费用,Matrix,连边,Edu160E,矩阵,CF,流量,Problem,中为 From： https://www.cnblogs.com/ydtz/p/17916060.html