39-算法设计

7.6.2　算法设计

这是一个二分图多重匹配问题，可以用最大流解决。

（1）构建网络

根据输入的数据，建立二分图，每个代表团为X集合中的结点，每个会议桌为Y集合中的结点，增设源点s和汇点t。从源点s向每个x_i结点连接一条容量为该代表团人数r_i的有向边。从每个y_j结点向汇点t连接一条容量为该会议桌容量c_j的有向边。X集合中每个结点向Y集合中每个结点连接一条容量为1的有向边。创建混合网络。

（2）求网络最大流

（3）输出安排方案

如果最大流值等于源点s与X集合所有结点边容量之和，则说明X集合每个结点都有完备的多重匹配，否则无解。对于每个代表团，从X集合对应点出发的所有流量为1的边指向的Y集合的结点就是该代表团人员的安排情况（一个可行解）。即x_i结点在Y集合的所有流量为1的邻接结点就是代表团x_i的人员会议桌安排。