题目描述
农夫JOHN为牛们做了很好的食品,但是牛吃饭很挑食。每一头牛只喜欢吃一些食品和饮料而别的一概不吃。虽然他不一定能把所有牛喂饱，他还是想让尽可能多的牛吃到他们喜欢的食品和饮料。
农夫JOHN做了F (1<=F<=100) 种食品和准备了D(1<=D<=100)种饮料。他有N(1<=N<=100)头牛，现在已经知道他的每头牛是否愿意吃某种食物和喝某种饮料。农夫JOHN想给每一头牛一种食品和一种饮料,使得尽可能多的牛得到喜欢的食物和饮料。
每一件食物和饮料只能由一头牛来用。例如如果食物2被一头牛吃掉了,没有别的牛能吃食物2。
输入
第一行: 三个数:N, F和D。
第2..N+1行:每一行有两个数开始F_i和D_i,分别是第i头牛可以吃的食品数和可以喝的饮料数。接下来下F_i个整数是第i头牛可以吃的食品号，再下面的D_i个整数是第i头牛可以喝的饮料号码。
输出
文件输出仅一行为一个整数，表示最多可以喂饱牛的数目。
样例输入
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的边；
每头牛拆成两个点xi,yi，这两个点连一条容量为1的边；
这头牛的喜好食物向xi连一条容量为1的边，yi向喜好饮品连一条容量为1的边；
每个饮品向汇点连一条容量为1的边。
检验：
每头牛只能占用一个饮品和食品，所以把牛拆点。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define sqr(x) ((x)*(x))
#define ln(x,y) int(log(x)/log(y))
#define food(x) (1+x)
#define drink(x) (1+m1+x)
#define cow(x) (1+m1+m2+x)
#define cow1(x) (1+m1+m2+n+x)
using namespace std;
const char* fin="ex1611.in";
const char* fout="ex1611.out";
const int inf=0x7fffffff;
const int maxn=1007,maxm=maxn*10;
int n,m1,m2,i,j,k,ans=0;
int num,tot=1,fi[maxn],ne[maxm],la[maxm],va[maxm];
int bz[maxn],cnt[maxn];
void add_line(int a,int b,int c){
tot++;
ne[tot]=fi[a];
la[tot]=b;
va[tot]=c;
fi[a]=tot;
}
void add(int a,int b,int c){
add_line(a,b,c);
add_line(b,a,0);
}
int gap(int v,int flow){
int i,use=0,k;
if (v==num) return flow;
for (k=fi[v];k;k=ne[k])
if (va[k] && bz[v]==bz[la[k]]+1){
i=gap(la[k],min(va[k],flow-use));
use+=i;
va[k]-=i;
va[k^1]+=i;
if (use==flow || bz[1]==num) return use;
}
if (!--cnt[bz[v]]) bz[1]=num;
cnt[++bz[v]]++;
return use;
}
int main(){
scanf("%d%d%d",&n,&m1,&m2);
num=1+m1+m2+n+n+1;
for (i=1;i<=n;i++){
int iiii;
add(cow(i),cow1(i),1);
scanf("%d",&j);
scanf("%d",&iiii);
for (;j;j--){
scanf("%d",&k);
add(food(k),cow(i),1);
}
for (;iiii;iiii--){
scanf("%d",&k);
add(cow1(i),drink(k),1);
}
}
for (i=1;i<=m1;i++) add(1,food(i),1);
for (i=1;i<=m2;i++) add(drink(i),num,1);
cnt[0]=num;
while (bz[1]<num) ans+=gap(1,inf);
printf("%d",ans);
return 0;
} 启发
通过拆点来限制每头牛的贡献。