最大点权闭合子图
题意：
##题解：
这时一道非常模板的最大点权闭合子图问题。
但是，我们不知道最大点权闭合子图是什么。。。。。。
现在，有我来告诉你：
有一堆有权值的点，权值可以为正为负为零。
这些点有一些如图的相对顺序：
即，这个图中会有一些树！
图可能原本是这样的：
图具体长什么样无所谓，你只要知道这些图是没有圈的就可以了。
而所谓的闭合子图，就是这个图中的以任意一个点为根的树。
树可以不唯一，即两个闭合子图加起来还是一个闭合子图。
我们要求这个闭合子图节点的最大点权和
注意一点，这里的树，必须一直向下延伸，直到无法再延伸才行！！
比如下图中：
所以，清楚最大点权闭合子图的概念了吗？
那么，最大点权闭合子图和我们这题又有什么关系呢？
我们看这一题，每一个知识点都有一个智慧值，和一个智力消耗值。
那么，每一个点的收获就是智慧值-智力消耗值。这就是每一个点的权值！！
那么，下一个关键的信息：对于一个知识点，我们要学完他的预备知识点后才可以学习他。
画成图就是这种情况：
很奇妙，其实将边反过来我们就会发现这就是一棵树。
也就是说，我们要在图中找一个闭合子图，使其的的点权和值最大。反向建图！
即，最大点权闭合子图问题！！！！！！！！
下面给出最大点权闭合子图的算法：
网络流求解
建图：
1.对途中原先的边e(u,v) e.cap=inf
2.设置原点start,设置汇点end，设置变量sum=0
3.遍历节点，如果该节点i权值>0 则建边(start,i,权值) 同时sum+=权值
否则，建边(i,end,abs(权值))。
4.利用最大流算法求解该图的最小割：flow
5.return sum-flow;
OK，此题得解！！！
如果想知道为什么是这样的算法的话，推荐这篇博客：
https://www.cnblogs.com/TreeDream/p/5942354.html#_label1
他列出了，最为简单时的闭合子图，即可以画成二分图时的情况。 (二分图的情况建图倒是和最大点权独立集有点像啊)
在这里他介绍了算法的生成过程。建议画图跟着理解。
如果你看了，上面的博客，并且理解了最大权值闭合子图的算法的话。
那么你或许会发现，我上面少了一些分析。
我们的最大点权闭合子图，事实上是从权值大于零的节点中选根的。节点小于零的直接被我们忽视了。
因为，所谓的根其实就是我学的最后一个知识点。如果这个知识点的收获为负，那么我为什么学他？
故，直接忽略。
这部分有点画蛇添足吗？
京公网安备 11010502036488号