题目描述(ID:12188)
标题: Dining 奶牛食品 最大流
标签: 图结构 网络流
详情:
FJ的奶牛们只吃各自喜欢的一些特定的食物和饮料,除此之外的其他食物和饮料一概不吃。某天FJ为奶牛们精心准备了一顿美妙的饭食,但在之前忘记检查奶牛们的菜单,这样显然是不能不能满足所有奶牛的要求。但是FJ又不愿意为此重新来做,所以他他还是想让尽可能多的牛吃到他们喜欢的食品和饮料。
FJ提供了F (编号为1、2、…、F)种食品并准备了D (编号为1、2、…、D)种饮料, 他的N头牛(编号为1、2、…、N)都已决定了是否愿意吃某种食物和喝某种饮料。FJ想给每一头牛一种食品和一种饮料,使得尽可能多的牛得到喜欢的食物和饮料。
每一种食物和饮料只能由一头牛来用。例如如果食物2被一头牛吃掉了,没有别的牛能吃到食物2。


输入格式:
第一行包含三个用空格分开的整数N,F和D;1<=F<=100,1<=D<=100,1<=N<=100

接下来的N行描述每个奶牛的信息:第i+1行的前两个整数为F_i和D_i,接下来的F_i个整数表示奶牛i喜欢的食品编号,再接下来的D_i个整数表示奶牛i喜欢的饮料编号。
输出格式:
仅一行一个整数,表示FJ最多能让多少头奶牛吃到自己喜欢的食品和饮料。
提示: 输入数据表明:奶牛1喜欢的食物1、2;喜欢喝饮料3、1;奶牛2喜欢的食物2、3;喜欢喝饮料1、2;奶牛3喜欢的食物1、3;喜欢喝饮料1、2;奶牛4喜欢的食物1、3;喜欢喝饮料3;

那么下面的分配方法将是最优的:奶牛1不给食品和饮料;奶牛2分配食物2和饮料2;奶牛3分配食物1和饮料2;奶牛4分配食物3和饮料4。

想一想就能发现,这是一道简单的网络流的题目。同学戏称为“三分图匹配”[手动笑哭]做这道题的时候我们只需要把奶牛放在中间,把每个奶牛拆成两头,这两头之间的容量为1,以保证一头牛就连一个饮料和食品,把饮料和食品放在两旁再加上源点和汇点就可以开始做最大流了。


每头牛拆成x和x’,相互连1的边
源向食物连1的边,饮料向汇连1的边
然后牛和可以吃的饮料/食物互相连边
最大流为答案



题目大意:有F种食物,D种饮料
N头奶牛,只能吃某种食物和饮料(而且只能吃特定的一份)
一种食物被一头牛吃了之后,其余牛就不能吃了
第一行有N,F,D三个整数
接着2-N+1行代表第i头牛,前面两个整数是Fi与Di(食物与饮料的种类数量),接着是食物的种类与饮料的种类
要求输出最多分配能够满足的牛的数量

解题思路:建图,有2*n+f+d+2个顶点
0表示源点,2*n+f+d+1表示汇点
由源点指向食物,再由食物指向牛,牛再指向对应的饮料,饮料再指向汇点
当然要使每一头牛都对应每一份食物与饮料,所以应该牛i指向牛i再指向饮料,这样就可以避免一头牛只占用多份食物与饮料了(要点:拆点最大流)
全部是有向的边,而且权值全部为1
我在这里是1到f为食物点,f+1到f+2*n为牛点,f+2*n+1到f+2*n+d为饮料点
样例:

输入

4 3 3
2 2 1 2 3 1
2 2 2 3 1 2
2 2 1 3 1 2
2 1 1 3 3

输出

3

解释

牛 1: 食品从 {1,2}, 饮料从 {1,2} 中选
牛 2: 食品从 {2,3}, 饮料从 {1,2} 中选
牛 3: 食品从 {1,3}, 饮料从 {1,2} 中选
牛 4: 食品从 {1,3}, 饮料从 {3} 中选
一个方案是:
Cow 1: 不吃
Cow 2: 食品 #2, 饮料 #2
Cow 3: 食品 #1, 饮料 #1
Cow 4: 食品 #3, 饮料 #3
用鸽笼定理可以推出没有更好的解 (一共只有3总食品和饮料).当然,别的数据会更难.
登录并解答