【学习笔记】最大权闭合子图

最大权闭合子图

---

看到一篇很好的博客，终于会了这玩意儿！qwq 咱不来虚的哈，直接上正题

• 什么是最大权闭合子图：

  每个点有点权，点权和最大的闭合子图即为最大权闭合子图

• 如何求解

  先说结论：$S$ 向正权点连，边权为权值，$T$ 向负权点连，边权为权值绝对值。最大权闭合子图权值即为正权和 - 最大流。

  证明（半感性）：$S -> T$ 的流量就是损失。 尽量选正权点为起点，所以 $S$ 向正权点连。一个正权点选会导致后续选一些负权点，但我们不知道选当前正权点是否优，就先选上，顶多后面被负权点损失掉为 $0$，不会亏。

习题：

$Salty Fish$

显然的最大权闭合子图模型——选了某个苹果就要黑掉所有能控制它的摄像头。

建图：

• 摄像头和源点连，割掉表示黑掉
• 苹果和汇点连，割掉表示放弃
• 显然不可能两边都不割！

考虑模拟费用流。本质是贪心的选苹果，然后优先去流浅的摄像头；反过来看，摄像头也优先流深的苹果。

从下往上做，与深度有关就长链剖分，开一个 $map$，$mp[x, d]$ 维护 $x$ 子树中深度为 $d$ 的苹果还能提供多少流量，在每个摄像头处从深的流量选起，每种苹果只在所在长链的根处被合并一次，$O((n + m)logn)$

然而这题要直接继承重儿子的 $map$，不然就 $MLE$。。以后写代码也注意一点。

$Code$