BZOJ 1163/1339 [Baltic2008]Mafia


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1163

                http://www.lydsy.com/JudgeOnline/problem.php?id=1339

题意:一个 n 个点的无向图,每个点有点权,可以控制一个点,代价为点权,控制的点就不能跑啦,求让 ab 不联通的最小代价...


一眼拆点最小割啦,对于每个点拆成出点和入点,之间连控制费用,原图都连 inf,防止被割掉

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 1163/1339 [Baltic2008]Mafia


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,