二分图多重匹配问题,可以用最大流解决.
建立二分图,每个单位为X集合中的顶点,每个餐桌为Y集合中的顶点,增设附加源S和汇T.
1,从S向每个Xi顶点连接一条容量为该单位人数的有向边. 2,从每个Yi顶点向T连接一条容量为该餐桌容量的有向边. 3,X集合中每个顶点向Y集合中每个顶点连接一条容量为1的有向边.
求网络最大流,如果最大流量等于所有单位人数之和,则存在解,否则无解.对于每个单位,从X集合对应点出发的所有满流边指向的Y集合的顶点就是该单位人员的安排情况(一个可行解).
对于一个二分图,每个顶点可以有多个匹配顶点,称这类问题为二分图多重匹配问题.X,Y集合之间的边容量全部是1,保证两个点只能匹配一次(一个餐桌上只