hdu 4292 Food

Description
　　You, a part-time dining service worker in your college’s dining hall, are now confused with a new problem: serve as many people as possible.
　　The issue comes up as people in your college are more and more difficult to serve with meal: They eat only some certain kinds of food and drink, and with requirement unsatisfied, go away directly.
　　You have prepared F (1 <= F <= 200) kinds of food and D (1 <= D <= 200) kinds of drink. Each kind of food or drink has certain amount, that is, how many people could this food or drink serve. Besides, You know there’re N (1 <= N <= 200) people and you too can tell people’s personal preference for food and drink.
　　Back to your goal: to serve as many people as possible. So you must decide a plan where some people are served while requirements of the rest of them are unmet. You should notice that, when one’s requirement is unmet, he/she would just go away, refusing any service.

Input
　　There are several test cases.
　　For each test case, the first line contains three numbers: N,F,D, denoting the number of people, food, and drink.
　　The second line contains F integers, the ith number of which denotes amount of representative food.
　　The third line contains D integers, the ith number of which denotes amount of representative drink.
　　Following is N line, each consisting of a string of length F. ?e jth character in the ith one of these lines denotes whether people i would accept food j. “Y” for yes and “N” for no.
　　Following is N line, each consisting of a string of length D. ?e jth character in the ith one of these lines denotes whether people i would accept drink j. “Y” for yes and “N” for no.
　　Please process until EOF (End Of File).

Output
　　For each test case, please print a single line with one integer, the maximum number of people to be satisfied.

Sample Input

4 3 3
1 1 1
1 1 1
YYN
NYY
YNY
YNY
YNY
YYN
YYN
NNY

Sample Output

3

题目大意：给出客人数量，食物种类，饮品种类，每种食物和饮品的库存，还有每位顾客的要求。求出，最多能满足多少位客人的要求。

解题思路：跟poj 3281 Dining是一种类型的题目。 设置超级源点，连向所有的食物，容量为该食物的库存，设置超级汇点，使所有饮品指向超级汇点，容量为该饮品的库存。然后客户连接对应的食物和饮品，容量为1。

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; const int N = 20005; const int M = 200005; const int OF = 300; const int INF = 0x3f3f3f3f; const int FIN = 1999; typedef long long ll; int n, f, d, s, t; int ec, head[N], first[N], que[N], lev[N]; int Next[M], to[M], v[M]; void addEdge(int a,int b,int c) { to[ec] = b; v[ec] = c; Next[ec] = first[a]; first[a] = ec++; to[ec] = a; v[ec] = 0; Next[ec] = first[b]; first[b] = ec++; } int BFS() { int kid, now, f = 0, r = 1, i; memset(lev, 0, sizeof(lev)); que[0] = s, lev[s] = 1; while (f < r) { now = que[f++]; for (i = first[now]; i != -1; i = Next[i]) { kid = to[i]; if (!lev[kid] && v[i]) { lev[kid] = lev[now] + 1; if (kid == t) return 1; que[r++] = kid; } } } return 0; } int DFS(int now, int sum) { int kid, flow, rt = 0; if (now == t) return sum; for (int i = head[now]; i != -1 && rt < sum; i = Next[i]) { head[now] = i; kid = to[i]; if (lev[kid] == lev[now] + 1 && v[i]) { flow = DFS(kid, min(sum - rt, v[i])); if (flow) { v[i] -= flow; v[i^1] += flow; rt += flow; } else lev[kid] = -1; } } return rt; } int dinic() { int ans = 0; while (BFS()) { for (int i = 0; i <= t; i++) { head[i] = first[i]; } ans += DFS(s, INF); } return ans; } char c[205]; void input() { int a; for (int i = 1; i <= f; i++) { scanf(%d, &a); addEdge(s, i, a); } for (int i = 1; i <= d; i++) { scanf(%d, &a); addEdge(i + 3 * OF, t, a); } for (int i = 1; i <= n; i++) { addEdge(i + OF, i + 2 * OF, 1); } getchar(); for (int i = 1; i <= n; i++) { scanf(%s, c); for (int j = 0; j < f; j++) { if (c[j] == 'Y') { addEdge(j + 1, i + OF, 1); } } } for (int i = 1; i <= n; i++) { scanf(%s, c); for (int j = 0; j < d; j++) { if (c[j] == 'Y') { addEdge(i + 2 * OF, (j + 1) + 3 * OF, 1); } } } } int main() { while (scanf(%d %d %d, &n, &f, &d) == 3) { ec = 0; memset(first, -1, sizeof(first)); s = 0, t = FIN; input(); printf(%d , dinic()); } return 0; }
       
      
     
    
   

?