USACO The Perfect Stall

容易看出，cow和stall可以构成一个二分图，如果一个cow可以在某个stall中产奶，那么他它们之间就有一条边。
题目要求就是这个二分图的最大匹配。
由于点数很小，直接用Ford-Fulkerson算法就可以了。
不过求解二分图最大匹配还有一个匈牙利算法（wikipedia），有兴趣的读者可以自行学习。本人曾经学过，不过忘的差不多了。

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004 #define MXN (410)
005
006 int M,N;
007 int cap[MXN][MXN];
008 int source = 0;   //virtual source and sink
009 int sink;
010 //used in BFS
011 int queue[MXN];
012 int visit[MXN];
013 int prev[MXN];
014 int flow[MXN];  //the new find flow to each node
015 int head,tail;
016 //
017
018 void init()
019 {
020     scanf("%d%d\n",&N,&M);
021     int i,t,s;
022     for(i = 1;i <= N;i ++)
023     {
024         scanf("%d",&t);
025         while(t --)
026         {
027             scanf("%d",&s);
028             cap[i][s + N] = 1;
029         }
030     }
031     sink = M + N + 1;
032     for(i = 1;i <= N;i ++)
033         cap[source][i] = 1;
034     for(i = 1;i <= M;i ++)
035         cap[i + N][sink] = 1;
036 }
037
038 void enqueue(int n)
039 {
040     queue[tail ++] = n;
041 }
042
043 int dequeue()
044 {
045     return queue[head ++];
046 }
047
048 int get_min(int a,int b)
049 {
050     if(a < b)    return a;
051     return b;
052 }
053
054 int bfs()    //find an argument path
055 {
056     int now,i;
057     memset(visit,0,sizeof(visit));
058     head = tail = 0;
059     flow[source] = MXN;
060     enqueue(source);
061     visit[source] = 1;
062     while(head < tail)
063     {
064         now = dequeue();
065         for(i = sink;i >= source;i --)
066         {
067             if(cap[now][i] > 0 && !visit[i])
068             {
069                 enqueue(i);
070                 flow[i] = get_min(flow[now],cap[now][i]);
071                 visit[i] = 1;
072                 prev[i] = now;
073                 if(i == sink)
074                 {
075                     return flow[sink];
076                 }
077             }
078         }
079     }
080     return 0;
081 }
082
083 void solve()
084 {
085     int i;
086     int newflow;
087     int totmax = 0;
088     while(1)
089     {
090         newflow = bfs();
091         if(newflow == 0)    break;
092         for(i = sink;i > 0;i = prev[i])
093         {
094             cap[prev[i]][i] -= newflow;
095             cap[i][prev[i]] += newflow;
096         }
097         totmax += newflow;
098     }
099     printf("%d\n",totmax);
100 }
101
102 int main()
103 {
104     freopen("stall4.in","r",stdin);
105     freopen("stall4.out","w",stdout);
106     init();   
107     solve();
108     return 0;
109 }