网络流 24 题

目前进度：\(6/24\)。

负载平衡问题

Link

第一道网络流题，自己建出来模了。感觉这题应该属于比较简单的一类。

先说一下如何建模吧。首先对于 \(\forall i\in[1,n]\)，\(i\) 向 \(i-1\) 和 \(i+1\) （环意义下）连一条容量为 \(+\infty\)，花费为 \(1\) 的边。之后建立超级源点 \(S\)，向每个 \(i\) 连一条容量为 \(a_i\)，花费为 \(0\) 的边；超级汇点 \(T\)，每个 \(i\) 向其连一条容量为 \(\bar a\)，花费为 \(0\) 的边。

之后跑一边最小费用最大流即可。

然后再讲一下建模的思路吧。首先，想要相邻两边转移，自然就要向 \(i\) 的两侧连边。由于我们可以搬任意大小，因此容量为 \(+\infty\)，花费自然就是搬的个数，即单位花费为 \(1\)。然后我们考虑整张图的起始条件和终结条件。

起始条件：每个 \(i\) 有不同的 \(a_i\)。对于这个，我们建立超级源点，连向 \(i\) 的、容量为 \(a_i\) 的边即可。这样可以保证一开始，\(i\) 的入流一定是 \(a_i\)。花费自然是 \(0\)。

终结条件：我们要让每个 \(a_i\) 都达到平均值 \(\bar a\)。既然如此，我们计算出来 \(\bar a\)，每个 \(i\) 向 \(T\) 连一条容量为 \(\bar a\) 的边，可以保证每个点平均后不超过 \(\bar a\)。而由于 \(S\) 的出流和我们加的这些边流量相等，因此这几条边一定会跑满，最终最大流就是 \(\sum a_i\)，此时的最小费用就是答案。

飞行员配对方案问题

Link

这个题是经典模板——二分图最大匹配。

考虑如此建模：二分图内部的边，左部点向右部点连容量为 \(1\) 的边；建立超级源点 \(S\)，对于每个左部点连流量为 \(1\) 的边；建立超级汇点 \(T\)，每个右部点向其连流量为 \(1\) 的边。跑出最大流即可。

至于输出方案，则找出来残量为 \(0\) 的边即可。

分配问题

Link

二分图最大权匹配/二分图最小权匹配。

和上一题一样建模，只不过加上费用即可。最后跑一遍最小费用最大流和最大费用最大流即可。

运输问题

Link

\(S\) 连左部点费用 \(0\)，容量 \(a_i\)，右部点连 \(T\) 费用 \(0\)，容量 \(b_i\)，左右部点间连 \(a\rightarrow b\) 容量 \(+\infty\)，代价 \(c_{a,b}\)。

跑最小费用最大流和最大费用最大流即可。

圆桌问题

Link

左部点为 \(m\) 个单位，右部点为 \(n\) 个桌子。

超级源点 \(S\) 向左部点连容量为 \(r_i\) 的边，右部点向超级汇点 \(T\) 连容量为 \(c_i\) 的边，左右部点连容量为 \(1\) 的边。

跑最大流即可。

根据前面几个题可以总结一些不成熟的经验：点权的限制可以通过源/汇点与其连边的容量限制。

试题库问题

Link

左部点为 \(n\) 个试题，右部点为 \(k\) 个类型。

超级源点 \(S\) 向左部点连容量为 \(1\) 的边，右部点向超级汇点 \(T\) 连容量为 \(k_i\)（\(i\) 类型所需题数）的边。

左右部点之间按照类型连容量为 \(1\) 的边。

跑最大流即可。