[文章目录]
Description
有一个M * N的棋盘，有的格子是障碍。现在你要选择一些格子来放置一些士兵，一个格子里最多可以放置一个士兵，障碍格里不能放置士兵。我们称这些士兵占领了整个棋盘当满足第i行至少放置了Li个士兵, 第j列至少放置了Cj个士兵。现在你的任务是要求使用最少个数的士兵来占领整个棋盘。N,M<=100
有上下界最小流。
建关于行和列的二分图，源点向行连边，下界为Li，列向汇点连边，下界为Ci。可以放士兵的(x,y)x向y连上界为1的边。跑最小流即可。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int ss,tt,s,t,S,T,n,m;
bool vis[110][110];
int head[210],to[50000],nxt[50000],f[50000],cnt=1;
inline void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0;
}
int dis[210];
queue<int>q;
bool bfs()
{
memset(dis,-1,sizeof dis);
while(!q.empty()) q.pop();
q.push(s); dis[s]=0; int x;
while(!q.empty())
{
x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==-1)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int xx,tmp=flow;
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(f[i],tmp));
if(!xx) dis[to[i]]=-1;
f[i]-=xx; f[i^1]+=xx; tmp-=xx;
if(!tmp) return flow;
}
return flow-tmp;
}
int main()
{
int x,y,z,tmp=0,sum=0,ans;
scanf("%d%d%d",&n,&m,&z);
ss=n+m+1; tt=ss+1; S=tt+1; T=S+1;
for(int i=1;i<=n;++i)
{
scanf("%d",&x);
add(ss,i,inf);
add(S,i,x);
tmp+=x;
}
add(ss,T,tmp); sum+=tmp; tmp=0;
for(int i=1;i<=m;++i)
{
scanf("%d",&x);
add(i+n,tt,inf);
add(i+n,T,x);
tmp+=x;
}
add(S,tt,tmp); sum+=tmp; add(tt,ss,inf);
while(z--)
{
scanf("%d%d",&x,&y);
vis[x][y]=1;
}
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j) if(!vis[i][j])
add(i,j+n,1);
s=S; t=T; while(bfs()) sum-=dinic(s,inf);
if(sum)
{
puts("JIONG!");
return 0;
}
for(int i=head[tt];i;i=nxt[i]) if(to[i]==ss) ans=f[i^1],f[i]=f[i^1]=0;
for(int i=head[S];i;i=nxt[i]) f[i]=f[i^1]=0;
for(int i=head[T];i;i=nxt[i]) f[i]=f[i^1]=0;
s=tt; t=ss; while(bfs()) ans-=dinic(s,inf);
printf("%d",ans);
return 0;
}