hdu4292——Food（SAP+拆点）-白红宇

hdu4292——Food（SAP+拆点）

阅读量：2343 次

发布时间：2019-05-10

本文共 4180 字，大约阅读时间需要 13 分钟。

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

这题原理上和很相似，我用刚学的SAP模板套了一遍，发现以下几个问题（不敢相信我居然能发现）：

n是所有的点的个数，理论上n=des+1就行；

点的个数MAXN和边的个数很玄学，以我的知识水平不知道它们之间应该有什么样的关系，总之一开始边数是点数的4倍，WA，改成32倍就过了。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #define INF 0x3f3f3f3f#define MAXN 11000#define Mod 10001using namespace std;struct E{ int to, frm, nxt, cap;}edge[MAXN<<5];int head[MAXN], e, n, m, src, des;int dep[MAXN], gap[MAXN]; //gap[x]=y:说明残留网络中dep[i]=x的个数为yvoid addedge(int u, int v, int c){ edge[e].frm = u; edge[e].to = v; edge[e].cap = c; edge[e].nxt = head[u]; head[u] = e++; edge[e].frm = v; edge[e].to = u; edge[e].cap = 0; edge[e].nxt = head[v]; head[v] = e++;}int Q[MAXN];void BFS(int src, int des){ memset(dep, -1, sizeof(dep)); memset(gap, 0, sizeof(gap)); gap[0] = 1; //说明此时有1个dep[i] = 0 int front = 0, rear = 0; dep[des] = 0; Q[rear++] = des; int u, v; while (front != rear) { u = Q[front++]; //cout<
             <
              
                edge[S[i]].cap) { temp = edge[S[i]].cap; inser = i; } for (i=0; i!=top; ++i) { edge[S[i]].cap -= temp; edge[S[i]^1].cap += temp; } res += temp; top = inser; u = edge[S[top]].frm; } if (u != des && gap[dep[u] -1] == 0)//出现断层，无增广路 break; for (i = cur[u]; i != -1; i = edge[i].nxt)//遍历与u相连的未遍历结点 if (edge[i].cap != 0 && dep[u] == dep[edge[i].to] + 1) //层序关系， 找到允许 break; if (i != -1)//找到允许弧 { cur[u] = i; S[top++] = i;//加入路径栈 u = edge[i].to;//查找下一个结点 } else //无允许的路径，修改标号 当前点的标号比与之相连的点中最小的多1 { int min = n; for (i = head[u]; i != -1; i = edge[i].nxt) //找到与u相连的v中dep[v]最小的点 { if (edge[i].cap == 0) continue; if (min > dep[edge[i].to]) { min = dep[edge[i].to]; cur[u] = i; //最小标号就是最新的允许弧 } } --gap[dep[u]]; //dep[u] 的个数变化了 所以修改gap ++gap[dep[u] = min + 1]; //将dep[u]设为min(dep[v]) + 1, 同时修改相应的gap[] if (u != src) //该点非源点&&以u开始的允许弧不存在，退点 u = edge[S[--top]].frm; } } return res;}int main(){ int N,D,F,w; while(~scanf("%d%d%d",&N,&F,&D)) { //1~F,F+1~F+N,F+N+1~F+N+N,F+N+N+1~F+N+N+D src=0; des=F+N+N+D+1; n=des+1; //还有源点，汇点 e=0; memset(head,-1,sizeof(head)); for(int i=1;i<=F;++i) { scanf("%d",&w); addedge(src,i,w); } for(int i=1;i<=D;++i) { scanf("%d",&w); addedge(F+N+N+i,des,w); } for(int i=1;i<=N;++i) { addedge(F+i,F+N+i,1); } string op; for(int i=1;i<=N;++i) { cin>>op; for(int j=0;j
               
                >op; for(int j=0;j

转载地址：http://ktcvb.baihongyu.com/

你可能感兴趣的文章