题目描述
农夫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#include #include #include #include #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]
启发
通过拆点来限制每头牛的贡献。