P4174 [NOI2006] 最大获利 题解

· · 题解

这篇题解使用最大密度子图的思路。

题意简述

有 m 个用户群，每个用户群需要两个中转站，建造第 i 个中转站的代价是 p_i，若第 i 个用户群需要的两个中转站 a_i 和 b_i 都被修建了，则会产生 c_i 的贡献，求出贡献减代价的最大值。

思路

下文中 c(S, T) 表示割 (S,T) 的容量。

密度子图：对于一个图 G=(V,E) 的一个子图 G'=(V',E')，对于所有的 (a,b) \in E'，都满足 a \in V' 且 b \in V'，则 G' 是 G 的一个密度子图。

最大密度子图：所有密度子图中，\frac{|E'|}{|V'|} 最大的一个。

像这样的分式，通常使用 01 分数规划来求解最大值。

回顾 01 分数规划的过程，二分 \frac{|E'|}{|V'|}=g，看 |E'|-g \cdot |V'| 的值大于还是小于 0。

因为是最大密度子图，所以要最大化 |E'|-g \cdot |V'|，等价于最小化 g \cdot |V'|-|E'|。

最小化联想到最小割，直接求密度子图的边的数量不好求，可以运用补集的思想。

用密度子图的点集相关的边的数量减去密度子图和其他点的割边的数量，就是密度子图中边的数量。

和点集相关的边的数量显然等于 \frac{\sum_{u\in V'}d_u}{2}（d_u 表示点 u 的度数）。

因此密度子图中边的数量就是

\frac{\sum_{u \in V'}{d_u}-c(V',V-V')}{2}

则最小化

\sum_{u \in V'}{(g-\frac{d_u}{2})}+c(V',V-V')

但是这里除了割以外还多了一项，推式子得上式等于

\frac{1}{2} (\sum_{u \in V'}{(2g-d_u)}+c(V',V-V'))

将加号左边跟右边融合，让所有点向汇点连一条容量为 2g-d_u 的边即可。

注意 2g-d_u 有可能是负数，所以加上一个大数 U，对应的源点向所有点连一条容量为 U 的边。原图中的边容量都为 1。

总结：让 |E'|-g|V'| 最大，就是让 g|V'|-|E'| 最小，就是让 U \cdot n + 2g|V'|-2|E'| 最小。

所以求最小割即可，答案就是 $\frac{U \cdot n - c(S,T)}{2}$。 *** 对于此题，把用户群看成边，连接两个中转站。要想满足某个用户群，就要先建对应的两个中转站。 要最大化 $|E'|+|V'|$，跟上面的证明相比少了 $g$，那就当 $g=0$ 好了，所以不用二分，直接求解最小割即可。