最大权闭合子图
参考博客:https://www.cnblogs.com/dilthey/p/7565206.html
什么是最大权闭合子图?
给你一个图(数字表示点权)
让你在其中选点(选了就要跟着选它连向的点),使得权值最大,问选法。
如图最大权闭合子图为 7 => -1 => -3
如何求解?
我们可以用最小割求解。
我们把 S 向正权点连一条容量为权值的边,把负权点连一条容量为权值绝对值的边。
同时把原图的边权改为 INF,求最小割。
最大权闭合子图就是 S图,最大值就是 正权点和-最小割