题解：P4174 [NOI2006] 最大获利

· · 题解

复健ing...

应该就是最大权闭合子图。但是网上抽象讲解我真看不懂。

P2762 太空飞行计划问题 弱化版。

题意：有 n 个有代价物品。有 m 个需求形如取 A_i,B_i 物品会获得 C_i 收益。取一些物品使得收益与代价的差最大。

建模方法：

  1. 源点向 m 个需求连边，流量为收益。
  2. 需求 i 向所需物品 A_i,B_i 连边，流量为 +\infty。
  3. 物品向汇点连边，流量为代价。

然后求最小割，答案是所有需求收益的总和与最小割的差。

考虑证明建模的正确性。

首先此时最小割的意义在于：选择一些需求和物品割掉，使源点到汇点不存在流量，且消耗流量最小。

考虑需求中被割掉了的部分。此时源点不可能通过它们流到汇点，因此它们所连向的物品，割与不割不受影响。

而对于需求中没被割掉的剩余部分。它们所连向的物品必须都被割掉。那么未割需求和割掉物品可以作为一组问题的解，因为所有未割需求所连向的物品都被割掉了。

我们用需求的收益总和，减去部分需求的收益和部分物品的代价之和（即最小割），就会得到未割需求的代价与割掉物品的代价之差。

由于最小割是最小值，那么用一个收益总和（一个定值）减去，得到的就是答案的最大值。