BZOJ1458 士兵占领题解（最大流）

题目：BZOJ1458. 题目：有一个$n\ast m$的矩阵，有$k$个位置不能填.现在限制第$i$行至少填$C_i$格，第$i$列至少填$L_i$格，判定是否可以满足条件，并在满足条件时输出最少需要填的格子数. $1\le n,m\le 100$.

首先判定很容易，我们只考虑如何填最少的格子.

当然可以上下界网络流做，不过感觉上下界有些大材小用了.

考虑先把所有可以填的格子填上，我们记填入的数量为$sum$；然后考虑去掉最多的格子，记去掉的格子数量为$mx$，那么答案就是$sum-mx$.

显然$sum$是很好求的，考虑如何求$mx$.

考虑对每行建一个点，由源点往每个点连一条边，流量为这一行可以去掉格子的最大数量（将那些不能填的格子也考虑进去）；对每列建一个点，每个点向汇点连一条边，流量为这一列可以去掉格子的最大数量；若某个位置上的点$(i,j)$可以填，则由第$i$行向第$j$列连一条流量为$1$的边.最后跑一个最大流就是$mx$.

代码如下：

#include<bits/stdc++.h> using namespace std; #define Abigail inline void typedef long long LL; const int N=100,INF=(1<<30)-1; int n,m,sk,a[2][N+9],b[N+9][N+9],st,td; struct side{ int y,next,f; }e[N*(N+2)*2+9]; int lin[N*2+9],cs; void Ins(int x,int y,int v){e[++cs].y=y;e[cs].f=v;e[cs].next=lin[x];lin[x]=cs;} queue<int>q; int dis[N*2+9]; bool Bfs_div(int st,int td){ for (int i=1;i<=n;++i) dis[i]=0; dis[st]=1;q.push(st); while (!q.empty()){ int t=q.front();q.pop(); for (int i=lin[t];i;i=e[i].next) if (!dis[e[i].y]&&e[i].f) dis[e[i].y]=dis[t]+1,q.push(e[i].y); } return dis[td]; } int cur[N*2+9]; int Dfs_path(int k,int td,int flow){ if (k==td) return flow; int res=0; for (int &i=cur[k];i;i=e[i].next) if (dis[k]+1==dis[e[i].y]&&e[i].f){ int t=Dfs_path(e[i].y,td,min(flow,e[i].f)); flow-=t;res+=t; e[i].f-=t;e[i^1].f+=t; if (!flow) return res; } return res; } int Max_flow(int st,int td){ int res=0; for (;Bfs_div(st,td);res+=Dfs_path(st,td,INF)) for (int i=1;i<=n;++i) cur[i]=lin[i]; return res; } int ans,sum; Abigail into(){ scanf("%d%d%d",&n,&m,&sk); for (int i=1;i<=n;++i){ scanf("%d",&a[0][i]); a[0][i]=m-a[0][i]; } for (int i=1;i<=m;++i){ scanf("%d",&a[1][i]); a[1][i]=n-a[1][i]; } sum+=n*m; for (int i=1;i<=sk;++i){ int x,y; scanf("%d%d",&x,&y); if (!b[x][y]) --a[0][x],--a[1][y],--sum; if (a[0][x]<0||a[1][y]<0) ans=-1; b[x][y]=1; } } Abigail work(){ if (ans<0) return; cs=1; for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) if (!b[i][j]) Ins(i,j+n,1),Ins(j+n,i,0); st=n+m+1; for (int i=1;i<=n;++i) Ins(st,i,a[0][i]),Ins(i,st,0); td=n+m+2; for (int i=1;i<=m;++i) Ins(i+n,td,a[1][i]),Ins(td,i+n,0); n=td; ans=sum-Max_flow(st,td); } Abigail outo(){ ans<0?puts("JIONG!"):printf("%d\n",ans); } int main(){ into(); work(); outo(); return 0; }