bzoj1458

题解：

网络流

原点到行建边

行到列建边

列到汇点建边

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=205,M=N*N*2;
int num,k,dis[N],t,ans,q[M],fi[M],ne[M];
int zz[M],sl[M],n,m,a[N],b[N],f[N][N],x[N],y[N];
void jb(int x,int y,int z)
{
    ne[num]=fi[x];
    fi[x]=num;
    zz[num]=y;
    sl[num++]=z;
    swap(x,y);
    z=0;
    ne[num]=fi[x];
    fi[x]=num;
    zz[num]=y;
    sl[num++]=z;    
}
int bfs()
{
    memset(dis,0xff,sizeof dis);
    dis[1]=0;
    int l=0,r=1;
    q[1]=1;
    while (l<r)
     {
         int j=q[++l];
         for (int i=fi[j];i!=-1;i=ne[i])
          if (dis[zz[i]]<0&&sl[i]>0)
           {
               dis[zz[i]]=dis[j]+1;
               q[++r]=zz[i];
           }
     }
    if (dis[n]>0)return 1;
    return 0; 
}
int find(int x,int low)
{
    int b=0;
    if (x==n)return low;
    for (int i=fi[x];i!=-1;i=ne[i])
     if (sl[i]>0&&dis[zz[i]]==dis[x]+1&&(b=find(zz[i],min(low,sl[i]))))
      {
          sl[i]-=b;
          sl[i^1]+=b;
          return b;
      }
    return 0;  
}
int main()
{
    memset(fi,-1,sizeof fi);
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=n;i++)scanf("%d",&x[i]);
    for (int i=1;i<=m;i++)scanf("%d",&y[i]);
    for (int i=1;i<=n;i++)a[i]=m;
    for (int i=1;i<=m;i++)b[i]=n;
    for (int i=1;i<=k;i++)
     {
         int x,y;
         scanf("%d%d",&x,&y);
         a[x]--;b[y]--;
         f[x][y]=1;
     }
    for (int i=1;i<=n;i++)
     if (x[i]>a[i])
      {
          puts("JIONG!");
          return 0;
      } 
     else jb(1,i+1,a[i]-x[i]);
    for (int i=1;i<=m;i++)
     if (y[i]>b[i])
      {
         puts("JIONG!");
         return 0;
      }  
    else jb(i+n+1,n+m+2,b[i]-y[i]);  
    for (int i=1;i<=n;i++)
     for (int j=1;j<=m;j++)
      if (!f[i][j])jb(i+1,n+j+1,1);
    k=n*m-k; 
    n=n+m+2;  
    while (bfs())
     while (t=find(1,1e9))
      ans+=t;
    printf("%d
",k-ans);
}