「网络流 24 题」圆桌聚餐 - 题目 - LibreOJ

题解

加入源点 $s$ 和汇点 $t$,对于每个单位和每个桌子建点,从 $s$ 向每个单位 $i$ 连容量为 $r_i$ 的边,从每个桌子 $i$ 向 $t$ 连容量为 $c_i$ 的边,就可以保证人数的限制。
一个特殊的限制是同一单位的人不能分配到同一桌子。若无此限制,只需从每个单位 $i$ 都向每个桌子 $j$ 连一条容量为 $+\infty$ 的边,即可完成分配。有此限制时,只需将这些边的容量都变成 $1$。
找到最大流后,若最大流量等于总人数 $\sum r_i$ (即 $s$ 的所有出边满流)则方案合法。对于每个单位,只需输出所有有流的出边到达的桌子的编号。

代码

loj6004_flow24.cpp
补作业好痛苦。。