hdu 4294 第一发SAP-白红宇

hdu 4294 第一发SAP

阅读量：6104 次

发布时间：2019-06-21

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

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int INF=0x7f7f7f7f;const int maxn=10008;struct fuck{    int u,v,flow,cap,next;}edge[maxn<<4];int head[maxn];int dep[maxn],gap[maxn];int tol;int last;void init(){    tol=0;    memset(head,-1,sizeof(head));}int scan()  {      int res = 0, ch, flag = 0;        if((ch = getchar()) == '-')             //判断正负          flag = 1;        else if(ch >= '0' && ch <= '9')           //得到完整的数          res = ch - '0';      while((ch = getchar()) >= '0' && ch <= '9' )          res = res * 10 + ch - '0';        return flag ? -res : res;  }  void addedge(int u,int v,int w){    edge[tol].u=u;    edge[tol].v=v;    edge[tol].cap=w;    edge[tol].flow=0;    edge[tol].next=head[u];    head[u]=tol++;    edge[tol].u=v;    edge[tol].v=u;    edge[tol].cap=0;    edge[tol].flow=0;    edge[tol].next=head[v];    head[v]=tol++;}void bfs(){    memset(dep,-1,sizeof(dep));    memset(gap,0,sizeof(gap));    gap[0]=1;    queue
         
              q;    int u,v,i;    q.push(last);dep[last]=0;    while(!q.empty())    {        u=q.front();q.pop();        for(i=head[u];i!=-1;i=edge[i].next)        {            v=edge[i].v;            if(edge[i].cap!=edge[i].flow||dep[v]!=-1)    continue;            q.push(v);            dep[v]=dep[u]+1;            ++gap[dep[v]];        }    }}int sap(){    int max_flow=0,i,u,v;    bfs();        int cur[maxn];    int S[maxn];    int top=0;    for(i=0;i<=last;i++)        cur[i]=head[i];    u=0;    while(dep[0]<=last)    {        if(u==last)        {            int temp=INF;            int inser;            for(i=0;i
          
           edge[S[i]].cap-edge[S[i]].flow) { temp=edge[S[i]].cap-edge[S[i]].flow; inser=i; } for(i=0;i
           
            edge[i].flow&&dep[u]==dep[edge[i].v]+1) break; if(i!=-1) { cur[u]=i; S[top++]=i; u=edge[i].v; } else { int mi=last+1; for(i=head[u];i!=-1;i=edge[i].next) { if(edge[i].cap==edge[i].flow) continue; if(mi>dep[edge[i].v]) { mi=dep[edge[i].v]; cur[u]=i; } } --gap[dep[u]]; dep[u]=mi+1; ++gap[dep[u]]; if(u!=0) u=edge[S[--top]].u; } } return max_flow;}int main(){ int i,j,n,F,D,u,v,w; char s[maxn]; while(scanf("%d%d%d",&n,&F,&D)==3) { init(); for(i=1;i<=F;i++) { scanf("%d",&w); //w=scan(); addedge(0,i,w); } last=F+D+(n<<1)+1; for(i=1;i<=D;i++) { scanf("%d",&w); //w=scan(); addedge(i+F,last,w); } for(i=1;i<=n;i++) { scanf("%s",s); int id=(i<<1); for(j=0;j