洛谷题面
这是一道关于网络流的建模题目
首先如果用最大流考虑,发现很难建出这个图,所以放弃
然后考虑用最小割考虑
我们发现题目中要我们求出最小价值,那么按照最大价值=总的价值-最小损失,我们需要建出一个图,求出其最小割
那么就尝试建图吧
1.只考虑个人价值
按照套路,我们建立一个源点\(S\)和汇点\(T\)
设割完后在\(S\)集中的点选择文科,在\(T\)集中的点选择理科
那么我们就把每个点向\(S\)和\(T\)连边,边权为这个人选文理科的愉悦值
就像这样
2.重难点:考虑两个人同时选择一科时候的奖励
我们考虑为这个额外奖励建立一条边,暂且称其为"奖励边"
按照题设条件,可以得到一个显然的结论:对于一条同时选择S集的奖励边,如果奖励边对应的两个人有一个和T还有连边,我们必须保证这条奖励边被割掉;同样地,对于都选T的奖励边也是如此
还有还有:选择这个额外奖励和将对应两个点选入对应集合是依赖的,相当于是对方的充要条件,因此,我们必须保证奖励边和两个对应点的关系牢不可破,不妨再整一条边,叫做关系边,将它的值赋为+∞,这样就可以保证在割边时这条关系边始终不会被断掉,这样就保证了它们的依赖关系
那么,我们就会想到一种建图的方法了,考虑让奖励边和关系边关联在一起,那么我们就再开一个节点作为中介吧
于是建出来的图大概是这样的
然后再对这张图跑一下最小割(也就是最大流)即可
代码也不难的,网络流的题关键是建模,就不贴码了
标签：最小,选择,奖励,考虑,国家集训队,我们,happiness From： https://www.cnblogs.com/sheepcsy/p/16623001.html