前言
写完了这道题我好想刚明白一点最小割???UU好闪,拜谢UU。
题解
首先,我们可以发现若第 \(i\) 行的 \(B\) 没选,那么第 \(i\) 列的 \(B\) 也不选,所以此时对于行和列是等价的。
若 \(A_i\) 是 \(0\),则会减少贡献 \(\sum_{j}B_{i, j}\)。否则会减少贡献 \(C_i\)。当 \(A_i\) 是 \(0\) 但 \(A_j\) 是 \(1\) 的时候,我们会减少贡献 \(B_{j, i}\) 的贡献。所以就可以建模了。
如下图
其中位于 \(S\) 区域的行和列表示 \(A\) 为 \(1\),会选上;\(T\) 区域的行和列表示 \(A\) 为 \(0\),不会选上。
主要的精华是:最小割所割出的容量是当前不同的点属于 \(S,T\) 集合状态下我们的花费。图中的最大流只在求最小割的时候用到了,没有实际的意义。
标签:UU,题解,行和列,最小,贡献,线性代数 From: https://www.cnblogs.com/jueqingfeng/p/17879481.html