【bzoj1458】士兵占领(最大流||有源汇最大流)

转载

http://hzwer.com/2963.html

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

4
数据范围
M, N <= 100, 0 <= K <= M * N

题解

此题的思路是先放满棋盘，然后考虑最多可以删多少个。。。

某一行和某一列的可以放的格子数小于需求就直接jiong掉
然后从源向每一行连边,流量为可以放的格子数 – 需求的格子数(也就是可以删多少格子)
从每一列向汇,同上.
从每一个非障碍的格子的行向列连边流量为1
跑一遍最大流即可ans=可放格子数-maxflow

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #define T 201

 #define inf 0x7fffffff

 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;

 }

 using namespace std;

 int n,m,K,cnt=,tot,ans;

 int l[],c[],a[],b[];

 bool mp[][];

 int q[],h[],head[],cur[];

 struct data{int to,next,v;}e[];

 void ins(int u,int v,int w)

 {e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;}

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

 {ins(u,v,w);ins(v,u,);}

 bool bfs()

 {

     int t=,w=;

     for(int i=;i<=T;i++)h[i]=-;

     q[]=;h[]=;

     while(t!=w)

     {

         int now=q[t];t++;

         for(int i=head[now];i;i=e[i].next)

             if(e[i].v&&h[e[i].to]==-)

             {

                 h[e[i].to]=h[now]+;

                 q[w++]=e[i].to;

             }

     }

     if(h[T]==-)return ;

     return ;

 }

 int dfs(int x,int f)

 {

     if(x==T)return f;

     int w,used=;

     for(int i=cur[x];i;i=e[i].next)

     {

         if(e[i].v&&h[e[i].to]==h[x]+)

         {

             w=f-used;

             w=dfs(e[i].to,min(e[i].v,w));

             e[i].v-=w;

             if(e[i].v)cur[x]=i;

             e[i^].v+=w;

             used+=w;if(used==f)return f;

         }

     }

     if(!used)h[x]=-;

     return used;

 }

 void dinic()

 {while(bfs()){for(int i=;i<=T;i++)cur[i]=head[i];ans+=dfs(,inf);}}

 int main()

 {

     m=read();n=read();K=read();

     int x,y;

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

         l[i]=n-read();

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

         c[i]=m-read();

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

     {

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

         mp[x][y]=;

         a[x]++;b[y]++;

         if(a[x]>l[x]){printf("JIONG!");return ;}

         if(b[y]>c[y]){printf("JIONG!");return ;}

     }

     tot=n*m-K;

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

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

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

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

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

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

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

     dinic();

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

     return ;

 }

 #include <stdio.h>

 #include <iostream>

 #include <algorithm>

 #include <memory.h>

 #include <map>

 using namespace std;

 typedef long long LL;

 const int maxn = ;

 const int maxm = ;

 const int inf = <<;

 int n,m,K,S,T,cnt,ecnt=,ehead[maxn],du[maxn];

 int g[maxm][maxm],row[maxn],col[maxn];

 struct edge {

     int u,v,vol,next;

 }edg[maxn];

 void add(int u,int v,int vol)

 {

     edg[++ecnt]=(edge){u,v,vol,ehead[u]};

     ehead[u]=ecnt;

     edg[++ecnt]=(edge){v,u,,ehead[v]};

     ehead[v]=ecnt;

 }

 namespace dinic

 {

     int lab[maxn],que[maxn],head,tail;

     int dfs(int u,int cur,int T)

     {

         int res=;

         if (u==T) return cur;

         for (int v,j=ehead[u];j&&res<cur;j=edg[j].next)

         if (edg[j].vol&&lab[v=edg[j].v]==lab[u]+) {

             int tmp=dfs(v,min(cur-res,edg[j].vol),T);

             edg[j].vol-=tmp;edg[j^].vol+=tmp;res+=tmp;

         }

         if (!res) lab[u]=-;

         return res;

     }

     bool bfs(int S,int T)

     {

         memset(lab,-,sizeof(int)*(cnt+));

         que[head=tail=]=S;lab[S]=;

         while (head<=tail)

         {

             int u=que[head++];

             for (int v,j=ehead[u];j;j=edg[j].next)

             if (edg[j].vol&&lab[v=edg[j].v]==-)

                 {lab[v]=lab[u]+;que[++tail]=v;}

         }

         return lab[T]!=-;

     }

     int dinic(int S,int T)

     {

         int res=;

         while (bfs(S,T)) res+=dfs(S,inf,T);

         return res;

     }

     int main()

     {

         int sS=++cnt,sT=++cnt;

         int ocnt=ecnt;

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

         {

             if (du[i]>) add(i,sT,du[i]);

             if (du[i]<) add(sS,i,-du[i]);

         }

         add(T,S,inf);dinic(sS,sT);

         int res=edg[ecnt].vol;

         for (int j=ehead[sS];j;j=edg[j].next)

             if (edg[j].vol) return -;

         for (int j=ocnt+;j<=ecnt;j++)

             edg[j].vol=;

         return res-dinic(T,S);

     }

 }

 int main()

 {

     scanf("%d %d %d",&n,&m,&K);

     S=++cnt;T=++cnt;

     for (int i=;i<=n;i++) row[i]=++cnt;

     for (int i=;i<=m;i++) col[i]=++cnt;

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

         scanf("%d",&x),du[row[i]]-=x,du[S]+=x,add(S,row[i],m);

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

         scanf("%d",&x),du[col[i]]+=x,du[T]-=x,add(col[i],T,n);

     for (int u,v,i=;i<=K;i++)

         scanf("%d %d",&u,&v),g[u][v]=;

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

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

         if (!g[i][j]) add(row[i],col[j],);

     int ans=dinic::main();

     if (ans!=-) printf("%d",ans);else puts("No Solution");

     return ;

 }

巴特西