LOJ 6004 – 圆桌聚餐

题面链接:LOJ 6004

建立这样一张二分图:左边是公司,右边是餐桌。左边的每个点都向右边的所有点建边,容量为1,代表一个公司最多有一个人去同一张桌子。源点连向左边的所有点,边权为公司人数,右边所有的点连向汇点,边权为桌子最多容纳人数。接着跑最大流可以得到一个最大的匹配,如果最大的流量(最多能安排多少人)小于总人数,那么不存在可行方案,否则存在。存在可行方案时,按照残量网络构造出方案:遍历所有边,当这个边是从左半部指向右半部的时候就说明左边这个公司要去一个人到右边这个桌子。

 

说点什么

avatar
50
  Subscribe  
提醒