CF 2400~3000 flows 板刷

CF62E World Evil

远古 2700。

给定 \(n\times m\) 网格图，每条边有容量。令第一列为源点，第 \(m\) 列为汇点，求最大流。\(n\le 5,m\le 10^5\)。

最大流转最小割，然后状压 DP 即可。\(dp[i][S]\) 表示前 \(i\) 列阻断了 \(S\) 内的行的最小代价。

CF103E Buying Sets

给定 \(n\) 个集合，每个集合有属性 \(a_i\)。题目保证对于任意的 \(k\)，任意 \(k\) 个集合，它们并的大小 \(\ge k\)。
求一个集合选法，要求它们的并大小等于选的个数，最大化所选的集合属性之和。

2900，比较有意思的题。

容易想到把集合作为左部点，元素作为右部点，集合向它包含的元素连边。问题转化为给定一张二分图，在左部选若干个点，满足右边被覆盖的点的个数与左边选的个数相等，求最大和。

因为任意 \(k\) 个集合的并大小 \(\ge k\)，所以如果给每个元素赋权值 \(-\infty\)，每个集合赋权值 \(+\infty\)，那最优解肯定恰好是集合与元素个数相等。于是转化为最大权闭合子图问题，容易使用网络流解决。

但是这题没完，题解区给出了一种即使不满足任意 \(k\) 个集合并的大小 \(\ge k\) 的条件也能做的方法。