标签：收益 源点 最小 汇点 Subsequence 权值 割断 Best
- “最大权值闭合图，即给定一张有向图，每个点都有一个权值（可以为正或负或0），你需要选择一个权值和最大的子图，使得子图中每个点的后继都在子图中。”
- 这样的定义可以让你理解算法执行的逻辑，却难以在你赛场上遇到它时牵动你的思绪
- 更符合你做题时真切感受的描述应该是：给你一些点，消耗一些点的代价可以得到另一些点的收益，要求收益最大化。 设想情境
- 前置思考：最小割模型中两个集合的性质分别由源点和汇点刻画；求出最小割后，边权再无意义，我们只关心图的连通情况
- 建模方法是：提取模型，点的取否类似于最小割中的点集划分，A->B类似于最小割中的“防止割断”；点边转化，把点的权值体现在边上；正负分类，源点连接收益点，汇点连接代价点（考虑到边权非负）；源点为超级置位点，汇点为超级重置点，这样，割断s->x意味着不选某个收益点；割断y->t意味着选择某个代价点，两者均使得总收益减少，故要求最小割，初始所有的边都未被割断，对于s，意味着选择所有收益点；对于t，意味着不选所有代价点，得到初始收益
标签：收益,
源点,
最小,
汇点,
Subsequence,
权值,
割断,
Best
From： https://www.cnblogs.com/watersail/p/18514688