【BZOJ1458】士兵占领 最大流的模板题

我们只要把他们可以有的限制用流量限制，再用两者关系限制一下就可以开心的跑了。

#include <cstdio>

#include <cstring>

#include <iostream>

#define r register

#define N 1005

using namespace std;

inline int read()

{

         r  int sum=;

         r  char ch=getchar();

         while(ch<''||ch>'')ch=getchar();

         while(ch>=''&&ch<='')

         {

                     sum=(sum<<)+(sum<<)+ch-'';

                     ch=getchar();

         }

         return sum;

}

int g[N][N];

struct VIA

{

        int to,next,w;

}c[N<<];

int head[N<<],t=;

int n,m,k;

inline void add(int x,int y,int z)

{

        c[++t].to=y;

        c[t].next=head[x];

        head[x]=t;

        c[t].w=z;

}

int L[N],C[N],LL[N],CC[N],S,T;

int deep[N<<],q[N<<],top,tail;

inline bool bfs()

{

        memset(deep,,sizeof(deep));

        q[]=S;

        top=tail=;

        deep[S]=;

        while(top<=tail)

        {

            r  int x=q[top++];

            if(x==T)return ;

            for(int i=head[x];i;i=c[i].next)

            if(c[i].w&&deep[c[i].to]==)

            {

                deep[c[i].to]=deep[x]+;

                q[++tail]=c[i].to;

            }

        }

        return ;

}

inline int Min(int x,int y)

{

        return x<y?x:y;

}

int dfs(int x,int v)

{

         if(x==T||!v)return v;

         r  int ret=;

         for(r  int i=head[x];i;i=c[i].next)

         if(c[i].w&&deep[c[i].to]==deep[x]+)

         {

                 r  int f=Min(v,c[i].w);

                 r  int w=dfs(c[i].to,f);

                 v-=w;

                 ret+=w;

                 c[i].w-=w;

                 c[i^].w+=w;

                 if(!v)break;

         }

         if(!ret)deep[x]=-;

         return ret;

}

inline int dinic()

{

        r  int ans=;

        while(bfs())ans+=dfs(S,0x7f7f7f7f);

        return ans;

}

int main()

{

      r  int ans=;

        n=read(),m=read(),k=read();

    for(r  int i=;i<=n;++i)L[i]=read(),LL[i]=m,ans+=L[i];

    for(r  int i=;i<=m;++i)C[i]=read(),CC[i]=n,ans+=C[i];

    for(r  int i=,x,y;i<=k;++i)x=read(),y=read(),g[x][y]=,--LL[x],--CC[y];

    for(r  int i=;i<=n;++i)

          if(L[i]>LL[i])

              {

                   printf("JIONG!\n");

                   return ;

              }

    for(r  int i=;i<=m;++i)

            if(C[i]>CC[i])

                {

                     printf("JIONG!\n");

                   return ;

                }

    S=n+m+,T=m+n+;

    for(r  int i=;i<=n;++i)

        for(r  int j=;j<=m;++j)

            if(!g[i][j])

                add(i,j+n,),add(j+n,i,);

    for(r  int i=;i<=n;++i)

        add(S,i,L[i]),add(i,S,);

    for(r  int i=;i<=m;++i)

        add(i+n,T,C[i]),add(T,n+i,);

    ans-=dinic();

    printf("%d\n",ans);

}