【bzoj1458】士兵占领

Description

有一个M * N的棋盘，有的格子是障碍。现在你要选择一些格子来放置一些士兵，一个格子里最多可以放置一个士兵，障碍格里不能放置士兵。我们称这些士兵占领了整个棋盘当满足第i行至少放置了Li个士兵, 第j列至少放置了Cj个士兵。现在你的任务是要求使用最少个数的士兵来占领整个棋盘。

Input

第一行两个数M, N, K分别表示棋盘的行数，列数以及障碍的个数。第二行有M个数表示Li。第三行有N个数表示Ci。接下来有K行，每行两个数X, Y表示(X, Y)这个格子是障碍。

Output

输出一个数表示最少需要使用的士兵个数。如果无论放置多少个士兵都没有办法占领整个棋盘，输出”JIONG!” (不含引号)

Sample Input

4 4 4
1 1 1 1
0 1 0 3
1 4
2 2
3 3
4 3

Sample Output

题解：

　　最大流第一题。orz黄学长。

　　问最小需要点数转化一下，就是最大能不放的位置。以S为原点，向每行连一条容量为n-l[i]-在该行上不能放置点数，以T为汇点，每列向T连一条m-c[i]-在该列上不能放置数的边。再把每行对应的点与可以连接的列对应点连一条容量为1的边，最大流显然就是要求的最大数。

　　然后用总点数减去这些就行。

 #include<cstdio>

 #include<cstring>

 const int T=;

 const int S=;

 inline int min(int a,int b){return a<b?a:b;}

 inline int read(){

     char ch=getchar();

     int f=,x=;

     while(!(ch>=''&&ch<='')){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+(ch-'');ch=getchar();}

     return x*f;

 }

 int m,n,k;

 const int N=;

 int l[N],c[N];

 bool vis[N][N],used[N];

 int rel[N],rec[N];

 int tot,ans;

 struct edges {

     int v,cap;edges *last;

 }edge[N<<],*head[N<<],*cur[N<<];int cnt;

 inline void insert(int u,int v,int w){

     edge[cnt].v=v;edge[cnt].last=head[u];edge[cnt].cap=w;head[u]=edge+cnt;cnt++;

     edge[cnt].v=u;edge[cnt].last=head[v];edge[cnt].cap=;head[v]=edge+cnt;cnt++;

 }

 int q[N<<];

 int dis[N<<];

 int h,t;

 bool bfs(){

     memset(dis,,sizeof(dis));

     dis[S]=,q[]=S;h=t=;

     int u,v;

     while(h<=t){

         u=q[h++];

         for(edges *i=head[u];i;i=i->last)

             if(i->cap&&!dis[i->v])

                 dis[i->v]=dis[u]+,q[++t]=i->v;

     }

     if(dis[T]) return ;

     else return ;

 }

 int dfs(int u,int w){

     if(u==T||w==) return w;

     int ret=;

     for(edges *i=head[u];i;i=i->last)if(i->cap&&(dis[i->v]==dis[u]+)){

         int f=dfs(i->v,min(i->cap,w));

         i->cap-=f,edge[(i-edge)^].cap+=f;

         w-=f,ret+=f;

         if(!w) break;

     }

     if(!ret) dis[u]=-;

     return ret;

 }

 inline int dinic(){

     int ret=;

     while(bfs()) ret+=dfs(S,0x7fffffff);

     return ret;

 }

 int main()

 {

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

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

         l[i]=n-read();

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

         c[i]=m-read();

     for(int i=,x,y;i<=k;i++)

     {

         x=read(),y=read();

         vis[x][y]=;

         rel[x]++,rec[y]++;

         if(rel[x]>l[x]){puts("JIONG!");return ;}

         if(rel[y]>l[y]){puts("JIONG!");return ;}

     }

     tot=n*m-k;

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

         insert(,i,l[i]-rel[i]);

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

         insert(m+i,T,c[i]-rec[i]);

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

         for(int j=;j<=n;j++)

             if(!vis[i][j])insert(i,j+m,);

     ans=dinic();

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

 }

秒客网