题目描述
W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E={E1，E2，…，Em}，和进行这些实验需要使用的全部仪器的集合I={I1，I2，…In}。实验Ej需要用到的仪器是I的子集RjÍI。配置仪器Ik的费用为ck美元。实验Ej的赞助商已同意为该实验结果支付pj美元。W教授的任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。
对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划。
口胡题解
给定一个有向图，点有点权，选择一个子图，满足子图上如果选择了一个点就必须选择它后继的所有点，这个子图就叫最大权闭合子图。
说人话，就是进入一个状态后他后面的操作你必须要进行，不论优还是劣，求最大收益。
当然如果全是正边那直接选整个图就行，我们考虑存在负边权情况。
RT,此图的最大权闭合子图应该是（6，-1），权和为5.
这东西我们现在知道了，可以用网络流这样处理：
把正边权和超源连边，负边权和超汇连边，容量为点权绝对值，这个图跑个最小割（最大流）即为答案。
这东西建图在网络流里真的算简单的，但是你咋证呢？？
（根据扶苏博客进行理解）
先讲一下定义： 在最小割图上，如果割掉 ss 和 uu （正权） 之间的边，代表不选择 uu 进入子图，如果割掉 vv （负权） 和 tt 之间的边，代表选择 vv 进入子图。
由于原图中的边全部是正无穷，最小割只会割掉源点和正权点之间或负权点和汇点之间的边。
先证明建图的正确性
考虑如果选择了正权点 uu ，为了保证 s-ts−t 不连通，必须割掉 uu 所有后继中的负权点。这证明了如果选择了一个正权点那么所有的后继负权点都会被选择。
若选择正权点 uu ，则任意与 uu 连边的非负权点 vv 都会通过无限容量的边与其连接，保证当 uu 不被割时， vv 也不会被割。
再证明所得图为最大权闭合
最小割得到的答案是啥？是被割正边与被割负边的最小集合。
即不选择的正边和选择的负边的最小集合（原因参考定义）。
我们要求的最大权闭合不就是找 正点权和-最小（不选择的正边和被选择的负边） 吗！
于是得证~
但最后打印方案卡了好久。
本来想直接输出最终满流的点，但发现他俩好像没关系。。
发现答案其实是最终与源点连通的所有点，也就是最小割的补集？？
然后直观做法就是把这条边给删了再跑网络流，若当前答案+满流=实际答案说明你这个边在答案中。。但感觉好慢。。
还有的说最终分层图里面还存在深度的就是最终与源点连通的点集，想想也对但是我 Dinic 不是这样写的啊。。
不管了。。