Food

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 76    Accepted Submission(s): 47

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

 

 

Recommend

liuyiding

 

 

 

很裸的最大流的题。和POJ 3182 很相似。

用SAP算法不会超时，比较高效。

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int MAXN=11000;const int MAXM=405000;const int INF=0x3f3f3f3f;struct Node{    int from,to,next;    int cap;}edge[MAXM];int tol;int head[MAXN];int dep[MAXN];int gap[MAXN];int n;void init(){    tol=0;    memset(head,-1,sizeof(head));}void addedge(int u,int v,int w){    edge[tol].from=u;    edge[tol].to=v;    edge[tol].cap=w;    edge[tol].next=head[u];    head[u]=tol++;    edge[tol].from=v;    edge[tol].to=u;    edge[tol].cap=0;    edge[tol].next=head[v];    head[v]=tol++;}void BFS(int start,int end){    memset(dep,-1,sizeof(dep));    memset(gap,0,sizeof(gap));    gap[0]=1;    int que[MAXN];    int front,rear;    front=rear=0;    dep[end]=0;    que[rear++]=end;    while(front!=rear)    {        int u=que[front++];        if(front==MAXN)front=0;        for(int i=head[u];i!=-1;i=edge[i].next)        {            int v=edge[i].to;            if(edge[i].cap!=0||dep[v]!=-1)continue;            que[rear++]=v;            if(rear>=MAXN)rear=0;            dep[v]=dep[u]+1;            ++gap[dep[v]];        }    }}int SAP(int start,int end){    int res=0;    BFS(start,end);    int cur[MAXN];    int S[MAXN];    int top=0;    memcpy(cur,head,sizeof(head));    int u=start;    int i;    while(dep[start]
          
           edge[S[i]].cap)              {                  temp=edge[S[i]].cap;                  inser=i;              }            for(i=0;i
           
            dep[edge[i].to]) { min=dep[edge[i].to]; cur[u]=i; } } --gap[dep[u]]; dep[u]=min+1; ++gap[dep[u]]; if(u!=start)u=edge[S[--top]].from; } } return res;}int g[2000][2000];char str[1200];int main(){ int start,end; int N,F,D; int u; int i; while(scanf("%d%d%d",&N,&F,&D)!=EOF) { memset(g,0,sizeof(g)); init(); n=F+D+2*N; start=0; end=n+1; for(i=1;i<=F;i++) { scanf("%d",&g[0][i]); addedge(0,i,g[0][i]); } for(i=F+2*N+1;i<=F+2*N+D;i++) { scanf("%d",&g[i][end]); addedge(i,end,g[i][end]); } for(i=1;i<=N;i++) addedge(F+2*i-1,F+2*i,1); for(i=1;i<=N;i++) { scanf("%s",&str); for(int j=0;j