BZOJ 1163/1339 [Baltic2008]Mafia

发布于 2017-06-21  128 次阅读


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

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

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


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

 


一个非常弱的准退役OIER