BZOJ 1711 [Usaco2007 Open]Dining 吃饭

发布于 2017-05-26  205 次阅读


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

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


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

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

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

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

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

 


一个非常弱的准退役OIER