企业官网建设流程全解析

牛是如此挑剔的食客。每头牛对某些食物和饮料都有偏好，她不会吃其他的。

农夫约翰为他的牛做了美味的饭菜，但他忘了对照他们的喜好检查菜单。虽然他可能不能让每个人都吃饱，但他想给尽可能多的奶牛提供一顿完整的食物和饮料。

农夫约翰烹制了F（1≤F≤100）类食物和D（1≤D≤100）类饮料。他的每头n（1≤n≤100）奶牛都决定了她是否愿意吃某种特定的食物或喝某种特定的饮料。农场主约翰必须为每头奶牛指定一种食物和一种饮料类型，以最大限度地增加奶牛的数量。

每道菜或饮料只能由一头奶牛食用（即，一旦将食品类型2分配给一头奶牛，就不能将其他奶牛分配给食品类型2）。

Input

第1行：三个空格分隔的整数：n、F和D

第2行..N+1：每行我以两个整数fi和di开头，我喜欢的菜品数量和我喜欢的饮料数量。接下来的fi整数表示我要吃的菜，后面的di整数表示我要喝的饮料。

Output

第1行：一个整数，它是可以同时喂养符合其意愿的食物和饮料的奶牛的最大数量。

Sample Input

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

Sample Output

3

Hint

One way to satisfy three cows is:
Cow 1: no meal
Cow 2: Food #2, Drink #2
Cow 3: Food #1, Drink #1
Cow 4: Food #3, Drink #3
The pigeon-hole principle tells us we can do no better since there are only three kinds of food or drink. Other test data sets are more challenging, of course.

每头牛都只喜欢某几种食物和某几种饮料，每种食物和某种饮料只能给一头牛，一头牛只能得到一种食物和一种饮料，而且一头牛必须同时获得一种食物和一种饮料才能满足。

因为要分配两个东西,且两个东西还要同时满足，所以此题不能用二分图匹配。

可以运用无源汇拆点最大流，先建立源点s和汇点t，把s和食物连接，权值为食物的数量1。饮料和t连接，权值为饮料的数量1。一头牛拆分成两个点，两点之间的容量为1，确保一头牛就选一套食物和饮料的搭配

源点 s ---> 食物 ---> 牛(左) ---> 牛(右) ---> 饮料 ---> 汇点 t

#include<iostream> #include<queue> #include<algorithm> #include<cstring> #define INF 0x3f3f3f3f using namespace std; const int maxn=500; int e[maxn][maxn],flag[maxn],pre[maxn]; int c,f,d,n,s,t; bool bfs() { memset(flag,0,sizeof(flag)); memset(pre,-1,sizeof(pre)); queue<int> q; q.push(s); flag[s]=1; pre[s]=s; int now,next; while(!q.empty()) { now=q.front(); q.pop(); for(int i=0; i<=n; i++) { if(!flag[i]&&e[now][i]>0) { flag[i]=1; pre[i]=now; q.push(i); if(i==t) return 1; } } } return 0; } int Edmonds_Karp() { int max_flow=0,mi; while(bfs()) { mi=INF; for(int i=t; i!=s; i=pre[i]) { mi=min(mi,e[pre[i]][i]); } for(int i=t; i!=s; i=pre[i]) { e[pre[i]][i]-=mi; e[i][pre[i]]+=mi; } max_flow+=mi; } return max_flow; } int main() { while(cin>>c>>f>>d) { n=f+2*c+d+1; s=0,t=n; memset(e,0,sizeof(e)); for(int i=1; i<=f; i++) e[s][i]=1; //源点和食物相连 for(int i=1; i<=c; i++) e[f+2*i-1][f+2*i]=1; //牛拆点 for(int i=1; i<=d; i++) e[f+2*c+i][t]=1; //饮料汇点和相连 for(int i=1; i<=c; i++) { int fx,dx,x; cin>>fx>>dx; for(int j=0; j<fx; j++) { cin>>x; e[x][f+2*i-1]=1; } for(int j=0; j<dx; j++) { cin>>x; e[f+2*i][f+2*c+x]=1; } } cout<<Edmonds_Karp()<<endl; } return 0; }