【网络流】bzoj3901(?)Magic

题意： 给定一个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，这样一来，其实每个点在图中都只出现了一次。