洛谷 P2762 太空飞行计划问题

Posted by

题目链接

https://www.luogu.org/problemnew/show/P2762

题解

线性规划与网络流24题之二。
最小割。
源点向每一个实验连边,容量为赞助的费用。
每个仪器向汇点,容量为仪器的费用。
每个实验向所需要的仪器连边,容量为\(INF\)。
求出的最小割为没选上的实验的赞助(赞助比花费少)+选上的仪器的花费,用总的赞助费减去最小割即为选上的实验的赞助-选上的仪器的花费,即为结果。
最后要输出方案比较**,每次去掉一条边观察最大流的变化,以确定这条边在不在割集中,具体实现看代码。
这道题的一般模型为最大权闭合子图:
闭合子图:对于图\(G=(V,E)\)的一个子图\(G’=(V’,E’)\),若\(\forall x\in V’\),都有\(\forall (x,y)\in E’\),且都有\(y\in V’\),那么我们称子图\(G’\)为\(G\)的一个闭合子图。
最大权闭合子图:所有闭合子图中点权和最大的一个。
具体做法看这个博客:最大权闭合图 – Because Of You – 博客园

代码

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注