Food

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

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

YYN

NYY

YNY

YYN

NNY

Sample Output

除建图外，别的似乎就是模板

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <queue>
#include <algorithm>
using namespace std;

#define N 1000
#define INF 0x3f3f3f3f

int G[N][N], Layer[N];

bool BFS(int S, int E)
{
    queue<int>Q;
    Q.push(S);

    memset(Layer, 0, sizeof(Layer));
    Layer[S] = 1;

    while(Q.size())
    {
        int u = Q.front(); Q.pop();

        if(u==E) return true;

        for(int i=1; i<=E; i++)
        {
            if(Layer[i]==0 && G[u][i])
            {
                Layer[i]=Layer[u]+1;
                Q.push(i);
            }
        }
    }
    return false;
}


int DFS(int u, int MaxFlow, int E)
{
    if(u==E) return MaxFlow;

    int uflow=0;
    for(int i=1; i<=E; i++)
    {
        if(G[u][i] && Layer[u]+1==Layer[i])
        {
            int flow = min(G[u][i], MaxFlow-uflow);
            flow = DFS(i, flow, E);

            G[u][i] -= flow;
            G[i][u] += flow;
            uflow += flow;

            if(uflow==MaxFlow) break;
        }
    }

    if(uflow==0) Layer[u] = 0;

    return uflow;
}

int Dinic(int S, int E)
{
    int ans = 0;

    while(BFS(S, E))
        ans += DFS(S, INF, E);

    return ans;
 }


int main()
{
    int n, F, D;

    while(scanf("%d%d%d", &n, &F, &D)!=EOF)
    {
        int i, j, a[N], b[N];
        char s[N];

        memset(G, 0, sizeof(G));

        for(i=1; i<=F; i++)
            scanf("%d", &a[i]);
        for(i=1; i<=D; i++)
            scanf("%d", &b[i]);

        for(i=1; i<=n; i++)
            G[i][i+n] = 1;
        for(i=n*2+1; i<=n*2+F; i++)
            G[0][i] = a[i-2*n];
        for(i=n*2+F+1; i<=n*2+F+D; i++)
            G[i][n*2+F+D+1] = b[i-n*2-F];

        for(i=1; i<=n; i++)
        {
            scanf("%s", s);

            for(j=0; j<F; j++)
               if(s[j]=='Y')
                G[n*2+j+1][i] = 1;
        }

        for(i=1; i<=n; i++)
        {
            scanf("%s", s);

            for(j=0; j<=D; j++)
                if(s[j]=='Y')
                G[i+n][2*n+F+j+1] = 1;
        }

        printf("%d
", Dinic(0, 2*n+F+D+1));
    }
    return 0;
}

勿忘初心