

$5.$圆桌问题

题目

假设有来自 $m$ 个不同单位的代表参加一次国际会议。每个单位的代表数分别为 $r_i (i =1,2,……,m)$ 。

会议餐厅共有 $n$ 张餐桌，每张餐桌可容纳 $c_i (i =1,2,……,n)$ 个代表就餐。

为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法，给出满足要求的代表就餐方案。

对于给定的代表数和餐桌数以及餐桌容量，编程给出满足要求的代表就餐方案。

题解

将代表放在左边，餐桌放在右边。 考虑建模。 每个单位最多有 $r_i$ 个人可以就餐，那么从 $S$ 到点 $i$ 的流量最多为 $r_i$. 同样的道理右边集合中点 $j$ 到 $T$ 流量为 $c_i$. 由于一个餐桌中一个单位最多只能由一个代表，那么左边集合与右边集合中流量最多为 $1$. 那么我们跑最大流，然后如果流量 $<n$，那么肯定不满足方案数，输出 $0$,不然的话有解，每个单位输出流量跑满的边所指向的右边集合中的点就行了。