【学习笔记】最大权闭合子图
最大权闭合子图
看到一篇很好的博客,终于会了这玩意儿!qwq 咱不来虚的哈,直接上正题
什么是最大权闭合子图:
每个点有点权,点权和最大的闭合子图即为最大权闭合子图
如何求解
先说结论:$S$ 向正权点连,边权为权值,$T$ 向负权点连,边权为权值绝对值。最大权闭合子图权值即为正权和 - 最大流。
证明(半感性):$S -> T$ 的流量就是损失。 尽量选正权点为起点,所以 $S$ 向正权点连。一个正权点选会导致后续选一些负权点,但我们不知道选当前正权点是否优,就先选上,顶多后面被负权点损失掉为 $0$,不会亏。
习题:
$Salty Fish$
显然的最大权闭合子图模型——选了某个苹果就要黑掉所有能控制它的摄像头。
建图:
- 摄像头和源点连,割掉表示黑掉
- 苹果和汇点连,割掉表示放弃
- 显然不可能两边都不割!
考虑模拟费用流。本质是贪心的选苹果,然后优先去流浅的摄像头;反过来看,摄像头也优先流深的苹果。
从下往上做,与深度有关就长链剖分,开一个 $map$,$mp[x, d]$ 维护 $x$ 子树中深度为 $d$ 的苹果还能提供多少流量,在每个摄像头处从深的流量选起,每种苹果只在所在长链的根处被合并一次,$O((n + m)logn)$
然而这题要直接继承重儿子的 $map$,不然就 $MLE$。。以后写代码也注意一点。