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.
| Line 1: | One line with 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. |
| Line 2..N+1: | N lines, each corresponding 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. |
A single line with a single integer, the maximum number of milk-producing stall assignments that can be made.
周围一群大牛说是二分图的最大匹配，于是匈牙利算法应声而出。
然而我对这短小精悍的程序抱有一丝怀疑。以下为代码：
#include<iostream>
#include<cstring>
using namespace std;
int map[105][105];
int visit[105],flag[105];
int n,m;
bool dfs(int a) {
for(int i=1;i<=n;i++) {
if(map[a][i] && !visit[i]) {
visit[i]=1;
if(flag[i]==0 || dfs(flag[i])) {
flag[i]=a;
return true;
}
}
}
return false;
}
int main() {
while(cin>>n>>m) {
memset(map,0,sizeof(map));
for(int i=1;i<=m;i++) {
int x,y;
cin>>x>>y;
map[x][y]=1;
}
memset(flag,0,sizeof(flag));
int result=0;
for(int i=1;i<=n;i++) {
memset(visit,0,sizeof(visit));
if(dfs(i)) result++;
}
cout<<result<<endl;
}
return 0;
}在他的指导下，我学会了用网络流（呵呵，也是现学的，dinic不太会）来构建这种二分图的匹配。
那么我们虚设一个源点和汇点，并且设每条边（包括和源点、汇点相连的边）的权是1.
我们从源点出发，求出去汇点的最大流，那么这个最大流一定是最佳匹配。
以下是代码：（这个网络流模板我是用bfs写的）
/*
PROG:stall4
ID:juan1973
LANG:C++
*/
#include <cstdio>
#include <algorithm>
#include <memory.h>
using namespace std;
int n,m,tot,flow,cnt,aug,v,p,q,i,j,u;
int map[505][505],queue[20005],pre[505];
int main()
{
freopen("stall4.in","r",stdin);
freopen("stall4.out","w",stdout);
memset(map,0,sizeof(map));
scanf("%ld%ld",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%ld",&p);
for (j=1;j<=p;j++)
{
scanf("%ld",&q);
map[i][q+n]=1;
}
}
flow=0;cnt=n+m+1;
for (i=1;i<=n;i++) map[0][i]=1;
for (i=n+1;i<=m+n;i++) map[i][cnt]=1;
memset(queue,0,sizeof(queue));
while(1)
{
memset(pre,-1,sizeof(pre));
queue[1]=0;
for(p=1,q=1;p<=q;p++)
{
u=queue[p];
for(v=1;v<=cnt;v++)
if(pre[v]<0&&map[u][v]>0)
{
pre[v]=u;
queue[++q]=v;
}
if(pre[cnt]>=0)break;
}
if(pre[cnt]<0)break;
aug=2000000000;
for(v=cnt;v!=0;v=pre[v])aug=min(aug,map[pre[v]][v]);
for(v=cnt;v!=0;v=pre[v])
{
map[pre[v]][v]-=aug;
map[v][pre[v]]+=aug;
}
flow+=aug;
}
printf("%ld\n",flow);
return 0;
}
usaco training 4.2.2 The Perfect Stall 最佳牛栏 题解,布布扣,bubuko.com
usaco training 4.2.2 The Perfect Stall 最佳牛栏 题解
原文：http://blog.csdn.net/jiangshibiao/article/details/19984081