本文共 345 字，大约阅读时间需要 1 分钟。

二刷了,复习一下网络流,因为这题实在太经典了。

①.做法一:一对关系建立一个虚点

这种做法比较简单。

源点连向每个人流量为选文科的价值,每个人连向汇点为选理科的价值

对于某两个人同时选文/理科能额外得到$val$的收益怎么办??

这里以文科为例,假如两个人同时选择文科说明连向理科的边都断掉了

这其实我们新建虚点$k$,源点连向$k$流量为$val$,$k$连向这两个人流量为$inf$

这样就造成,任何一个人选择理科,也就是保留了人到汇点的边,那么$k$就能到汇点必须割掉$val$

正确性显然,累加初始收益,减去最小割就是答案。

②.做法二:模型转换解方程组

这里引用一下nofind的题解

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/115359575 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！