网络流 24 题做题记录

网络流 24 题做题记录

P3254 圆桌问题

源点连单位，容量为单位人数，桌子连汇点，容量为桌子容量，各单位连各桌子，容量为 \(1\)，因为每个单位在每张桌子上最多 \(1\) 人，跑最大流。

P2763 试题库问题

源点连试题，容量为 \(1\)，试题连对应种类，容量为 \(1\)，种类连汇点，容量为该种类需要试题数，跑最大流。

P4015 运输问题

源点连仓库，容量为货物数，费用 \(0\)；商店连汇点，容量为需要货物数，费用 \(0\)，仓库连商店，容量无穷大，费用为 \(c_{i,j}\)，跑最小费用最大流和最大费用最大流。

P4016 负载平衡问题

多于平均值的需要运出，于是从 \(s\) 连，容量为多出的部分，费用 \(0\)，少于的同理，相邻点连边，容量无限制，费用 \(1\)，跑最小费用最大流即可。

P4014 分配问题

和运输问题类似。