模拟费用流

简介

本质上就是用类似于堆或者 $dp$ 的东西来模拟费用流增广的过程

例题

1. 简要题意：现在有 $n$ 个人，要将这些人分成两个队伍，每个人只能属于一个队伍，如果将第 $i$ 个人分到第一个队伍，那么能够得到 $a_i$ 的收益，如果将第 $i$ 个人分到第二个队伍，那么将得到 $b_i$ 的收益，第一个队伍有 $p$ 个人，第二个队伍有 $s$，求收益最大的分配方案

   $n\le 3000$

   简要题解：容易得到费用流做法，建图：

   $s$ 连 $i$，容量为 $1$，费用为 $0$

   $i$ 连 $i_a$，容量为 $1$，费用为 $a_i$

   $i$ 连 $i_b$，容量为 $1$，费用为 $b_i$

   $i_a$ 连 $t_a$，容量为 $p$，费用为 $0$

   $i_b$ 连 $t_b$，容量为 $s$，费用为 $0$

   注意到这张图非常简单，我们考虑用堆来对其进行模拟，每次增广只有四种选择，选一个分到第一个队伍，选一个人分到第二个队伍，选一个人分到第一个队伍的同时将一个第一个队伍的人换到第二个队伍，选一个人分到第二队伍的同时，将一个第二队伍的人换到第一个队伍，拿四个堆模拟即可，时间复杂度 $O(n\log n)$

   2016-2017 ACM-ICPC, NEERC, Southern Subregional Contest I Olympiad in Programming and Sports