来源和评测点
USACO 2007 Open Gold
Poj3281
Caioj1116
题目
「题目大意」
有F(1≤F≤1000)块不同的肉(编号1~F)和D(1≤D≤1000)罐不同的饮料(编号1~D),N(1≤N≤1000)头(编号1~N)。
每头牛有自己喜欢的肉和饮料。每块肉和每罐饮料只能供给一头牛使用。
求最多能满足多少头牛能同时享用到自己喜欢的肉和饮料。
(注意某头牛得到满足,不要求享用自己所有喜欢的肉和饮料,
只要喜欢的肉的其中一块和自己喜欢的饮料其中一罐就可以算满足)
「输入格式」
第一行:三个整数N,F,D
接下来N行。每行描述一头牛。
每行开头两个整数Fi和Di,Fi表示该牛喜欢的肉的数目,Di表示它喜欢的饮料的数目。
接下来Fi个数,各表示它喜欢的肉的编号,再来Di个数,表示它喜欢的饮料的编号。
(注意Fi和Di有可能为0)
「输出格式」
一个整数,最大满足的牛的数目
「输入样例」
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
分析
网络流教程和题目分类参见:
「OI之路」03图论算法-4网络流
其他网络流题目参见:Tag-网络流
类似模板题
终极起点连接肉
肉连接牛
牛连接饮料
饮料连接终极终点
但还要拆点,为了让一头牛只能选一种,把一头牛分成两个,自己连自己
所有边权都是1,这样的最大流就是方案数
代码
|
|