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