POJ 3218 – Dining

题目链接:POJ 3218

网络流问题。建图方法:食物和牛之间建边,容量为1,牛和饮料之间建边,容量为1,把所有食物连到超级源,把所有饮料连到超级汇。这里要注意的是每个牛最多和一对食物和饮料匹配,所以牛代表的点有流量限制,可以拆点,限制容量为1。在这张图上跑最大流即可。

 

说点什么

avatar
50
  Subscribe  
提醒