牛是如此挑剔的食客。每头牛对某些食物和饮料都有偏好她不会吃其他的。农夫约翰为他的牛做了美味的饭菜但他忘了对照他们的喜好检查菜单。虽然他可能不能让每个人都吃饱但他想给尽可能多的奶牛提供一顿完整的食物和饮料。农夫约翰烹制了F1≤F≤100类食物和D1≤D≤100类饮料。他的每头n1≤n≤100奶牛都决定了她是否愿意吃某种特定的食物或喝某种特定的饮料。农场主约翰必须为每头奶牛指定一种食物和一种饮料类型以最大限度地增加奶牛的数量。每道菜或饮料只能由一头奶牛食用即一旦将食品类型2分配给一头奶牛就不能将其他奶牛分配给食品类型2。Input第1行三个空格分隔的整数n、F和D第2行..N1每行我以两个整数fi和di开头我喜欢的菜品数量和我喜欢的饮料数量。接下来的fi整数表示我要吃的菜后面的di整数表示我要喝的饮料。Output第1行一个整数它是可以同时喂养符合其意愿的食物和饮料的奶牛的最大数量。Sample Input4 3 3 2 2 1 2 3 1 2 2 2 3 1 2 2 2 1 3 1 2 2 1 1 3 3Sample Output3HintOne way to satisfy three cows is:Cow 1: no mealCow 2: Food #2, Drink #2Cow 3: Food #1, Drink #1Cow 4: Food #3, Drink #3The 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#includeiostream #includequeue #includealgorithm #includecstring #define INF 0x3f3f3f3f using namespace std; const int maxn500; 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)); queueint q; q.push(s); flag[s]1; pre[s]s; int now,next; while(!q.empty()) { nowq.front(); q.pop(); for(int i0; in; i) { if(!flag[i]e[now][i]0) { flag[i]1; pre[i]now; q.push(i); if(it) return 1; } } } return 0; } int Edmonds_Karp() { int max_flow0,mi; while(bfs()) { miINF; for(int it; i!s; ipre[i]) { mimin(mi,e[pre[i]][i]); } for(int it; i!s; ipre[i]) { e[pre[i]][i]-mi; e[i][pre[i]]mi; } max_flowmi; } return max_flow; } int main() { while(cincfd) { nf2*cd1; s0,tn; memset(e,0,sizeof(e)); for(int i1; if; i) e[s][i]1; //源点和食物相连 for(int i1; ic; i) e[f2*i-1][f2*i]1; //牛拆点 for(int i1; id; i) e[f2*ci][t]1; //饮料汇点和相连 for(int i1; ic; i) { int fx,dx,x; cinfxdx; for(int j0; jfx; j) { cinx; e[x][f2*i-1]1; } for(int j0; jdx; j) { cinx; e[f2*i][f2*cx]1; } } coutEdmonds_Karp()endl; } return 0; }
