本文共 1161 字，大约阅读时间需要 3 分钟。

$闭合子图指定义$

$在闭合子图中,每个点能到的所有点都在子图中$

$最大权闭合子图$

$在所有闭合子图中,点权最大的闭合子图$

最大权闭合子图常用最小割来解决

$点权正的和s源点相连,流量是点权$

$点权负的和汇点t相连,流量是点权的绝对值$

$其他边流量都是inf,代表不可以割掉$

$令sumn为正点权和,sumn-最大流(最小割)就是答案$

$其中由于是闭合子图,选1必须选择2和3$

$假如最小割割掉了s-1的边,代表不选择1号节点$

$假如最小割割掉了2-t和3-t,代表选择1,2,3节点$

$因为如果选择1号节点,就比如选择2,3节点$

$2,3节点点权是负数,所以割掉2,3相当于选择2，3$

$由此,满足闭合子图,减去最小割也满足点权最大.$

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/108227363 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！