1. 题目

传送门= ̄ω ̄=

2. 题解

前面发了这题的贪心解法,但是毕竟题目没给出总人数限制,所以不严谨。

这里再给出网络流解法吧。

建图的话就是从源点连一条容量为$r_i$的边到第$i$个单位,再从第$i$个桌子连一条容量为$c_i$的边到汇点,最后从每个单位连一条容量为1的边到每个桌子。

再跑最大流。

如果残量网络中有从源点到某个单位的边没有满流则说明无解,输出0。

否则对于每个单位,如果从该单位到某个桌子的原先容量为1的边满流了,则说明该单位用了这张桌子。

代码: