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
3
Source
建图与POJ3281一毛一样，边开少了狂T。。。
1 //2017-08-24 2 #include3 #include 4 #include 5 #include 6 #include 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 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\n", dinic.maxflow());118 } 119 return 0;120 }