模拟费用流

模拟费用流是什么

考虑一般的单路增广费用流流程，就是一直去寻找最小/最大费用增广路的过程。但是寻找一条增广路往往需要最短路算法，这造成了很大的时间开销。找到增广路的方式不唯一，可以通过别的手段去寻找增广路。在一些特殊网络中可以获得更加优秀的时间复杂度。

QOJ 7185

题目描述

有 \(n\) 个学生和 \(k\) 门科目，第 \(i\) 个学生选择第 \(k\) 门科目的消耗为 \(a_{i,j}\) 。第 \(i\) 门科目至多被 \(b_i\) 个学生选择。希望求出每一个学生选择恰好一门科目的最小消耗和。

\(n \leq 5\times 10^4 ,k \leq 10\) 。

思路点拨

看到这个题目很容易想到一个网络流建模：

• 一个源点，一个汇点，\(n\) 个代表学生的节点，\(k\) 个代表科目的节点。

• 学生节点向源点连流量为 \(1\) ，代价为 \(0\) 的边。

• 科目节点向汇点连流量为 \(b_i\) ，代价为 \(0\) 的边。

• 第 \(i\) 个同学向第 \(j\) 个科目练流量为 \(1\) ,代价为 \(a_{i,j}\) 的边。

最终该网络的最小费用最大流就是正确答案，这里不多做讲述。相比之下我们更加关心图的性质以及增广路的形态。

经过观察，图具有如下性质：

• 图是一张二分图，那么每一条增广路除了源点和汇点之外都是左-右-左交替的。

• 最短路本身的性质：不会经过相同的节点（该网络图不存在负环）。

• 关键性质：注意到结合上述两个性质，每一条增广路的长度都是 \(O(k)\) 级别的，因为右部点的数量很少。

我们将一次增广路径画出来：