当前位置: 代码迷 >> 综合 >> 【网络流】bzoj3901(?)Magic
  详细解决方案

【网络流】bzoj3901(?)Magic

热度:50   发布时间:2023-09-27 09:11:17.0

题意:
给定一个n点,m边的有向图,每个点有一个ai和一个bi
每个点的代价,定义为:这个点所有的出边中,ai最大的一个
你可以在代价中加bi,使当前节点的ai为0

题解:
首先,如果你和我一样想到费用流,那么最好及时弃掉。。。。
正解是最小割:
我们把a和b拆开来看,换句话说,每个点a,b分别维护一个节点
对每一个点,可以构造如下图
【网络流】bzoj3901(?)Magic
【网络流】bzoj3901(?)Magic
其中满足aj>ak>…>an
这里可以手动推一下,发现(以图1为例):
假设割掉ak,那么必须满足bj必须被割掉
假设割掉an,那么必须满足bj…b(n-1)都被割掉
满足题目的要求
在实现中,可以忽略掉图1中由S连向i,流量为INF的边,改为直接由S连向j点,流量为aj,这样一来,其实每个点在图中都只出现了一次。

  相关解决方案