网络流24题-5 圆桌问题
把单位放在一边,餐桌放在一边,然后增加一个超级源点,从这个点到每个单位有一条边,容量是这个单位的人数,增加一个超级汇点,从每个餐桌到这个点有一条边,容量是餐桌能够容纳的人数,然后每个单位到每个餐桌连一条边,容量为1,表示所有的餐桌最多只能有同一个单位的1个人,然后跑一次最大流,如果为满流,也就是所有的人都有相应的餐桌,那么就存在一种方案满足题意.另外这题可以贪心,每次选人数最多的单位分配餐桌,对同一个单位,每个餐桌分配一个人,然后下次分配的时候,首先选那些剩下座位多的餐桌,依次下去,就可以判定是不是存在一种方案了.本题就不贴代码了.
