[最大流]USACO 2002 Winter Green：New Years Party 解題報告

題目鏈接：http://oj.jzxx.net/problem.php?id=1674
代碼發芽網代碼高亮：http://fayaa.com/code/view/25178/

题目描述

A group of N (3 <= N <= 200) cows is having a New Year's party. Each cow is able to cook several different kinds of food (in units called a "dish"). There are a total of D (5 <= D <= 100) different kinds of food. Each kind of food is denoted by an integer in the range 1..D. The cowrdinator wants to maximize the total number of dishes brought to the party, but has specified a limit for the number of dishes of each type. Each cow can bring K (1 <= K <= 5) dishes, but they must be different from each other (she can't bring 3 bovine pies, for example, but she could bring a pie, some bread, and some nice alfalfa in orange sauce). What is the maximum amount of food that can be brought?

 

输入

* Line 1: Three integers: N, K, and D * Line 2: D non-negative integers: the limit on total number of each of the various dishes that can be brought to the party * Lines 3..N+2: Each line contains an initial integer Z (1 <= Z <= D) denoting the number of different dishes a cow can prepare; the rest of the line contains Z integers that are the food identifiers, food type 1 first, food type 2 second, etc..

输出

A single line with a single integer that is the maximum number of dishes that can be brought to the party.

样例输入

4 3 5 2 2 2 2 3 4 1 2 3 4 4 2 3 4 5 3 1 2 4 3 1 2 3

样例输出

9

提示

EXPLANATION OF SAMPLE INPUT:

data......     explanation...................................................

4 3 5          4 cows, each cow brings up to 3 dishes, 5 different food types

2 2 2 2 3      max for party of 2 dishes food types 1..4; 3 dishes of food 5

4 1 2 3 4      This cow can cook 4 different foods (1, 2, 3, 4)

4 2 3 4 5      This cow can cook 4 different foods (2, 3, 4, 5)

3 1 2 4        This cow can cook 3 different foods (1, 2, 4)

3 1 2 3        This cow can cook 3 different foods (1, 2, 3)

SAMPLE OUTPUT:
[Cow 1 brings foods 3 and 4; cow 2 brings foods 3, 4 and 5;
cow 3 brings foods 1 and 2; and cow 4 brings foods 1 and 2.]

来源

USACO 2002 Winter Green

【分析】
這是一道很好的最大流的題目～中文翻譯見劉汝佳、黃亮的《算法藝術與信息學競賽》P315。
為了構圖，需要把每頭奶牛、每種食品當作一個節點，記為Cow[a],Food[b]，如果第a頭奶牛會做第b種食品，則在Cow[a]，Food[b]之間連一條邊，權值為1。
然後設置一個源點和一個匯點，極為S和T。把每頭奶牛與S之間連一條邊，權值為K。
把每種食品和T之間連一條邊，權值為這種食品的上限。

現在，只需要對這個圖從S到T求最大流即可。
由於節點數一共才(N+D)個，所以使用Ford_Fulkerson方法求最大流即可。

【我的代碼】

0001 /*
0002 *Problem: New Years Party

0003 *Source:USACO 2002 Winter Green
0004 *Author: Yee-fan Zhu
0005 *School: Henan Experimental High School
0006 *GTalk: zyfworks@gmail.com
0007 */

0008 #include <iostream>
0009 #include <cstdlib>
0010 #include <cstdio>
0011 #include <queue>

0012 #include <cstring>
0013 using namespace std;
0014 
0015 const int INF=0x7ffffff; 

0016 const int MAXN_COW=201;
0017 const int MAXN_FOOD=101;

0018 
0019 int N; /*The Number of Cows*/
0020 int D; /*The Number of Food*/

0021 int K; /*Each Cow Can Bring K dishes*/
0022 
0023 int FL[MAXN_FOOD]; /*Food Limit*/

0024 int Cow[MAXN_COW]; 
0025 int Food[MAXN_FOOD];
0026 int Map[MAXN_FOOD+MAXN_COW+2][MAXN_FOOD+MAXN_COW+2];

0027 int Source;
0028 int Sink;
0029 int Ans=0;

0030 
0031 int Node=0;
0032 
0033 void Add_Edge(int x,int y,int v)

0034 {
0035     Map[x][y]=v;
0036 }
0037 
0038 void Init_Graph()

0039 {
0040     memset(Map,0,sizeof(Map));
0041     scanf("%d %d %d\n",&N,&K,&D);

0042 
0043     for (int i=1;i<=N;i++)
0044     {

0045         Node++;
0046         Cow[i]=Node;
0047     }
0048     for (int i=1;i<=D;i++)

0049     {
0050         Node++;
0051         Food[i]=Node;
0052     }

0053 
0054     Node++;
0055     Source=Node;
0056     Node++;

0057     Sink=Node;
0058 
0059     for (int i=1;i<=D;i++)

0060         scanf("%d",&FL[i]);
0061 
0062     for (int i=1;i<=N;i++)

0063         Add_Edge(Source,Cow[i],K);
0064     for (int i=1;i<=D;i++)

0065         Add_Edge(Food[i],Sink,FL[i]);
0066 
0067     int FN,x;

0068     for (int i=1;i<=N;i++)
0069     {
0070         scanf("%d",&FN);

0071         for (int j=1;j<=FN;j++)
0072         {
0073             scanf("%d",&x);

0074             Add_Edge(Cow[i],Food[x],1);
0075         }
0076     }
0077 }

0078 
0079 bool Used[MAXN_FOOD+MAXN_COW+2];
0080 int Father[MAXN_FOOD+MAXN_COW+2];

0081 void Ford_Fulkerson()
0082 {
0083     while(1)
0084     {

0085         queue<int>Q;
0086         memset(Used,0,sizeof(Used));
0087         memset(Father,0,sizeof(Father));

0088 
0089         int now;
0090         Used[Source]=true;

0091         Q.push(Source);
0092         while(!Q.empty())
0093         {
0094             now=Q.front();

0095             Q.pop();
0096             if(now==Sink)
0097                 break;
0098             for (int i=1;i<=Node;i++)

0099             {
0100                 if(Map[now][i] && !Used[i])

0101                 {
0102                     Father[i]=now;
0103                     Used[i]=true;

0104                     Q.push(i);
0105                 }
0106             }
0107         }
0108 

0109         if(!Used[Sink])
0110             break;
0111 
0112         int u;

0113         int Min=INF;
0114         for (u=Sink;u!=Source;u=Father[u])

0115         {
0116             if(Map[Father[u]][u]<Min)
0117                 Min=Map[Father[u]][u];

0118         }
0119 
0120         for(u=Sink;u!=Source;u=Father[u])

0121         {
0122             Map[Father[u]][u]-=Min;
0123             Map[u][Father[u]]+=Min;

0124         }
0125 
0126         Ans+=Min;
0127     }
0128 

0129     printf("%d\n",Ans);
0130 }
0131 
0132 int main()

0133 {
0134     //freopen("party.in","r",stdin);
0135     //freopen("party.out","w",stdout);
0136     Init_Graph();

0137     Ford_Fulkerson();
0138     return 0;
0139 }
0140 
0141 /**************************************************************

0142     Problem: 1674
0143     User: 201107
0144     Language: C++
0145     Result: 正确

0146     Time:824 ms
0147     Memory:1640 kb
0148 ****************************************************************/