网络流 24 题

夏佑 | XiaU

目前进度:\(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\) 的边。

跑最大流即可。

  • 标题: 网络流 24 题
  • 作者: 夏佑 | XiaU
  • 创建于 : 2023-10-11 00:00:00
  • 更新于 : 2023-12-31 20:13:28
  • 链接: https://summace.cc/24-Problems-of-Network-Flow/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。