|
The Perfect Stall
Description Farmer John completed his new barn just last week, complete with all the latest milking technology. Unfortunately, due to engineering problems, all the stalls in the new barn are different. For the first week, Farmer John randomly assigned cows to stalls, but it quickly became clear that any given cow was only willing to produce milk in certain stalls. For the last week, Farmer John has been collecting data on which cows are willing to produce milk in which stalls. A stall may be only assigned to one cow, and, of course, a cow may be only assigned to one stall.
Given the preferences of the cows, compute the maximum number of milk-producing assignments of cows to stalls that is possible. Input The input includes several cases. For each case, the first line contains two integers, N (0 <= N <= 200) and M (0 <= M <= 200). N is the number of cows that Farmer John has and M is the number of stalls in the new barn. Each of the following N lines corresponds to a single cow. The first integer (Si) on the line is the number of stalls that the cow is willing to produce milk in (0 <= Si <= M). The subsequent Si integers on that line are the stalls in which that cow is willing to produce milk. The stall numbers will be integers in the range (1..M), and no stall will be listed twice for a given cow.
Output For each case, output a single line with a single integer, the maximum number of milk-producing stall assignments that can be made.
Sample Input 5 5 2 2 5 3 2 3 4 2 1 5 3 1 2 5 1 2 Sample Output 4 Source |
[Submit] [Go Back] [Status] [Discuss]
模板题~可用匈牙利算法，也可用最大流解决
AC Code：
View Code
#include <iostream> #include <queue> #include <cstdio> #include <cstring> #include <ctime> using namespace std; #define min(x, y) ((x) < (y) ? (x) : (y)) const int maxn = 405; const int inf = 0x7fffffff; int r[maxn][maxn]; //记录残留网络的容量 int flow[maxn]; //标记从源点到当前结点实际还剩多少流量可用 int pre[maxn]; //结点的前驱, 同时标记该节点是否在队列中 int n, m; int BFS(int s, int d) //使用BFS寻找增广路径 { queue<int> que; memset(pre, -1, sizeof(pre)); pre[s] = 0; flow[s] = inf; //初始化源点的流量为无穷大 que.push(s); while(!que.empty()) { int cur = que.front(); que.pop(); if(cur == d) break; //抵达汇点，找到增广路径 for(int i = 1; i <= d; ++i) //遍历所有的结点 { //原图是没有流向s的流的，但是在剩余网络中有反向边，故残留图中有到s的流，故须判断i != s if(i != s && r[cur][i] > 0 && pre[i] == -1) { pre[i] = cur; //记录前驱以保存路径 flow[i] = min(r[cur][i], flow[cur]); //关键：迭代地找到增量 que.push(i); } } } if(pre[d] == -1) return -1; //d没有前驱结点，即没有流能到达d，残留图中不再存在增广路径 else return flow[d]; } int EK(int s,int d) { int inc = 0; int max_flow = 0; while((inc = BFS(s, d)) != -1) { for(int i = d; i != s; i = pre[i]) //利用前驱寻找路径 { //以下两步更新残留图 r[pre[i]][i] -= inc; //改变正向边的容量 r[i][pre[i]] += inc; //改变反向边的容量 } max_flow += inc; } return max_flow; } int main() { int n, m, s, t; //n-cows, m-stalls，s-源点，t-汇点 while(scanf("%d %d", &n, &m) != EOF) { int a, b, i; s = 0; t = n + m + 1; memset(r, 0, sizeof(r)); for(i = 1; i <= n; i++) //i是牛的编号 { r[s][i] = 1; //源点和所有牛之间容量为1 scanf("%d", &a); while(a--) { scanf("%d", &b); r[i][b+n] = 1; //牛i能匹配棚b } } for(i = n + 1; i < t; i++) r[i][t] = 1; printf("%d\n", EK(s, t)); } return 0; }