相关文章
【学习笔记】最大权闭合子图
对于非 DAG 的图也能用最小割求解最大权闭合子图。
理解:对于一个环,如果正点权有一个没删的话,那么整个环是可达的(相邻的边的容量为 inf),这样环上所有负全点都会向汇点断边,同时为了满足最优…
建站知识
2025/1/24 5:46:58
最大权值闭合子图的证明详解
前面定义部分转自这篇博客
网络流——最小割求最大权闭合子图
定义
有一个有向图,每一个点都有一个权值(可以为正或负或0),选择一个权值和最大的子图,使得每个点的后继都在子图里面,这个子图就叫最大权闭…
建站知识
2025/1/14 3:35:37