题目分析

我们有：

• $m$ 个单位，第 $i$ 个单位有 $r_i$ 个代表
• $n$ 张餐桌，第 $j$ 张餐桌可容纳 $c_j$ 人
• 限制：同一个单位的代表不能在同一个餐桌就餐

要求判断是否存在可行方案，并输出一个方案。

建模思路

这是一个二分图匹配问题：

• 左部：$m$ 个单位
• 右部：$n$ 张餐桌
• 边的限制：每个单位可以向多个餐桌分配代表，但每个餐桌不能有来自同一单位的两个代表

更准确地说，这是二分图的多重匹配：

• 每个单位 $i$ 需要匹配 $r_i$ 次（即派出 $r_i$ 个代表）
• 每个餐桌 $j$ 最多匹配 $c_j$ 次（即容纳 $c_j$ 人）
• 同一个单位到同一个餐桌最多匹配 1 次（即同一个单位的代表不能在同一个餐桌）

网络流建图

1. 源点 $S$ 向每个单位 $i$ 连一条容量为 $r_i$ 的边，表示该单位有 $r_i$ 个代表需要安排。

2. 每个单位 $i$ 向每个餐桌 $j$ 连一条容量为 $1$ 的边，表示单位 $i$ 最多派 1 个代表到餐桌 $j$（满足"同一单位代表不在同一餐桌"）。

3. 每个餐桌 $j$ 向汇点 $T$ 连一条容量为 $c_j$ 的边，表示餐桌 $j$ 最多容纳 $c_j$ 人。

4. 求 $S$ 到 $T$ 的最大流。

可行性判断

如果最大流值等于总代表数 $\sum_{i=1}^m r_i$，则说明所有代表都能被安排，问题有解；否则无解。

输出方案

对于每个单位 $i$，遍历所有餐桌 $j$：

• 如果单位 $i$ 到餐桌 $j$ 的边上有流量（即流量为 1），说明单位 $i$ 有 1 个代表在餐桌 $j$ 就餐，将 $j$ 加入该单位的输出列表。

样例验证

输入：

4 5
4 5 3 5
3 5 2 6 4

• 总代表数：$4+5+3+5=17$
• 总容量：$3+5+2+6+4=20$（容量充足）

建图：

• $S$ → 单位1：容量4
• $S$ → 单位2：容量5
• $S$ → 单位3：容量3
• $S$ → 单位4：容量5
• 每个单位到每个餐桌：容量1
• 餐桌1 → $T$：容量3
• 餐桌2 → $T$：容量5
• 餐桌3 → $T$：容量2
• 餐桌4 → $T$：容量6
• 餐桌5 → $T$：容量4

最大流 = 17，有解。

输出方案（一种可能）：

1
1 2 4 5        # 单位1的代表在餐桌1,2,4,5
1 2 3 4 5      # 单位2的代表在餐桌1,2,3,4,5  
2 4 5          # 单位3的代表在餐桌2,4,5
1 2 3 4 5      # 单位4的代表在餐桌1,2,3,4,5

验证：

• 每个餐桌人数不超过容量
• 同一单位代表在不同餐桌

算法复杂度

• 节点数：$m + n + 2$
• 边数：$m + n + m \times n$（单位数+餐桌数+单位到餐桌的边）
• 使用 Dinic 算法：$O(V^2 E) = O((m+n)^2 \cdot m n)$
• 在 $m \leq 150, n \leq 270$ 时可行

总结

这道题通过将单位视为左部点、餐桌视为右部点，用容量为 1 的边保证同一单位代表不在同一餐桌，用源点到单位的容量限制代表数，餐桌到汇点的容量限制餐桌人数，将问题转化为最大流问题，简洁高效地解决了圆桌聚餐的安排问题。