警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「Codeforces 704D」Captain America - 上下界网络流

会考 RP++!

题意

传送门:Codeforces 704D - Captain America

给一个二维平面上的 \(n\) 个点,每个点可以染成红色或蓝色,染成红色代价 \(r\),蓝色代价 \(b\)\(m\) 条限制,每条限制是「某一 行/列 染成红色和蓝色点数的差的绝对值」的形式。最小化代价。

感觉没说清,还是看原题意吧……

解法

注意到这道题的题面里有以下信息:

  • 二维平面 / 棋盘
  • 行列限制
  • 每个点的可选方案是二元的(红蓝)

换句话说:

  • 二分图
  • 行列 对应 左端右端
  • 流量有无 对应 颜色红蓝

根据套路,每个点对应一条行连向列的边。

令第 \(i\) 行有 \(k_i\) 个点、\(f_i\) 个红点,这一行限制的最小值是 \(d_i\),那么有 \(|2f_i-k_i|\le d_i\)

\(\left\lceil\frac{k-d}2\right\rceil\le f\le\left\lfloor\frac{k+d}2\right\rfloor\),显然是上下界网络流。

令输入的点集为 \(P\),第 \(i\) 列有 \(k'_i\) 个点,这一列限制的最小值是 \(d'_i\),那么网络流建图为:

\[ \begin{cases} &S\xrightarrow{\left[\left\lceil\frac{k_i-d_i}2\right\rceil,\left\lfloor\frac{k_i+d_i}2\right\rfloor\right]}i\\ &i'\xrightarrow{\left[\left\lceil\frac{k'_i-d'_i}2\right\rceil,\left\lfloor\frac{k'_i+d'_i}2\right\rfloor\right]}T\\ &\forall_{(x,y)\in P},x\xrightarrow1y' \end{cases} \]

代码