HDU4292(KB11-H 最大流)

Food

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5945 Accepted Submission(s): 2010

Problem 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

Source

2012 ACM/ICPC Asia Regional Chengdu Online

建图与POJ3281一毛一样，边开少了狂T。。。

  1 //2017-08-24
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <iostream>
  5 #include <algorithm>
  6 #include <queue>
  7 #pragma comment(linker, "/STACK:1024000000,1024000000") 
  8 
  9 using namespace std;
 10 
 11 const int N = 2010;
 12 const int M = 200010;
 13 const int INF = 0x3f3f3f3f;
 14 int head[N], tot;
 15 struct Edge{
 16     int next, to, w;
 17 }edge[M];
 18 
 19 void add_edge(int u, int v, int w){
 20     edge[tot].w = w;
 21     edge[tot].to = v;
 22     edge[tot].next = head[u];
 23     head[u] = tot++;
 24 
 25     edge[tot].w = 0;
 26     edge[tot].to = u;
 27     edge[tot].next = head[v];
 28     head[v] = tot++;
 29 }
 30 
 31 struct Dinic{
 32     int level[N], S, T;
 33     void init(int _S, int _T){
 34         S = _S;
 35         T = _T;
 36         tot = 0;
 37         memset(head, -1, sizeof(head));
 38     }
 39     bool bfs(){
 40         queue<int> que;
 41         memset(level, -1, sizeof(level));
 42         level[S] = 0;
 43         que.push(S);
 44         while(!que.empty()){
 45             int u = que.front();
 46             que.pop();
 47             for(int i = head[u]; i != -1; i = edge[i].next){
 48                 int v = edge[i].to;
 49                 int w = edge[i].w;
 50                 if(level[v] == -1 && w > 0){
 51                     level[v] = level[u]+1;
 52                     que.push(v);
 53                 }
 54             }
 55         }
 56         return level[T] != -1;
 57     }
 58     int dfs(int u, int flow){
 59         if(u == T)return flow;
 60         int ans = 0, fw;
 61         for(int i = head[u]; i != -1; i = edge[i].next){
 62             int v = edge[i].to, w = edge[i].w;
 63             if(!w || level[v] != level[u]+1)
 64                   continue;
 65             fw = dfs(v, min(flow-ans, w));
 66             ans += fw;
 67             edge[i].w -= fw;
 68             edge[i^1].w += fw;
 69             if(ans == flow)return ans;
 70         }
 71         if(ans == 0)level[u] = -1;
 72         return ans;
 73     }
 74     int maxflow(){
 75         int flow = 0, f;
 76         while(bfs())
 77               while((f = dfs(S, INF)) > 0)
 78                 flow += f;
 79         return flow;    
 80     }
 81 }dinic;
 82 
 83 char str[N];
 84 
 85 int main()
 86 {
 87     //std::ios::sync_with_stdio(false);    
 88     //freopen("inputH.txt", "r", stdin);
 89     int n, f, d, w;
 90     while(scanf("%d%d%d", &n, &f, &d) != EOF){
 91         int s = 0, t = 2*n+f+d+2;
 92         dinic.init(s, t);
 93         for(int i = 1; i <= n; i++)
 94               add_edge(i, n+i, 1);
 95         for(int i = 1; i <= f; i++){
 96             scanf("%d", &w);
 97               add_edge(s, 2*n+i, w);
 98         }
 99         for(int i = 1; i <= d; i++){
100             scanf("%d", &w);
101               add_edge(2*n+f+i, t, w);
102         }
103         for(int i = 1; i <= n; i++){
104             scanf("%s", str);
105             for(int j = 0; j < f; j++){
106                 if(str[j] == 'Y')
107                     add_edge(2*n+j+1, i, 1);
108             }
109         }
110         for(int i = 1; i <= n; i++){
111             scanf("%s", str);
112             for(int j = 0; j < d; j++){
113                 if(str[j] == 'Y')
114                     add_edge(n+i, 2*n+f+j+1, 1);
115             }
116         }
117         printf("%d
", dinic.maxflow());
118     }    
119     return 0;
120 }