BZOJ 1711 [Usaco2007 Open]Dining 吃饭


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1711

题意:n 头牛,f 种食物,d 种饮料,一头牛一种食物一种饮料,求最大匹配...


不知道三分图最大匹配有没有什么神奇的做法... 不过直接最大流即可...

对于每头牛,拆点,拆开的点间连一条权值为 1 的边,以限制每头牛只能跑一次....

S 向食物点连 1,食物点向牛入点连 1,牛入点向牛出点连 1,牛出点向饮料点连 1,饮料点向 T 连 1,建图结束....

终于想出了一道题的建模.... 虽然水成这个样子... 代码如下:

对了... 貌似有一组范围犯规的数据,貌似 d=1009... 数组要开好大...

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 1711 [Usaco2007 Open]Dining 吃饭


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,