[BZOJ1458]士兵占领 - A-Failure的博客

题目

Description

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

Input

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

Output

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

Sample Input

Sample Output

数据范围

M, N <= 100, 0 <= K <= M * N

题解

用有源汇上下界最小流板子充数的我真是嗨到不行啊

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=1e5+5,N=105,inf=1e8;
struct p{
	int x,y,dis;
}c[MAX];
int n,m,num=1,k,t,ss,tt;
int h[MAX],H[MAX],qu[MAX],d[MAX],f[MAX];
bool use[MAX];
bool qwq[N][N];
int read()
{
	int x(0);
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
	return x;
}
bool bfs(int s,int t)
{
	qu[1]=s;
	memset(d,0,sizeof(d));
	int hl=1,tl=d[s]=1;
	while(hl<=tl)
	{
		int tt=qu[hl++];
		for(int i=h[tt];i;i=c[i].x)
		  if(c[i].dis&&!d[c[i].y])
		  {
		  	d[c[i].y]=d[tt]+1,qu[++tl]=c[i].y;
		  	if(c[i].y==t) return 1;
		  }
	}
	return 0;
}
int dfs(int x,int t,int dix=inf)
{
	if(x==t||!dix) return dix;
	int sum=0;
	for(int &i=H[x],dis;i;i=c[i].x)
	  if(d[c[i].y]==d[x]+1&&c[i].dis)
	  {
	  	dis=dfs(c[i].y,t,min(dix,c[i].dis));
	  	if(dis)
	  	{
	  		sum+=dis,dix-=dis,c[i].dis-=dis,c[i^1].dis+=dis;
	  		if(!dix) break;
		}
	  }
	if(!sum) d[x]=-2;
	return sum;
}
int Dinic(int s,int t)
{
	int tot=0,D;
	while(bfs(s,t))
	{
		memcpy(H,h,sizeof(h));
		while(D=dfs(s,t)) tot+=D;
	}
	return tot;
}
void add(int x,int y,int dis)
{
	c[++num]=(p){h[x],y,dis},h[x]=num;
	c[++num]=(p){h[y],x},h[y]=num;
}
int main()
{
	n=read(),m=read(),k=read(),t=n+m+1,ss=t+1,tt=ss+1;
	for(int i=1,x;i<=n;++i)
	  x=read(),add(0,i,inf-x),f[i]+=x,f[0]-=x;
	for(int i=n+1,x;i<=n+m;++i)
	  x=read(),add(i,t,inf-x),f[i]-=x,f[t]+=x;
	for(int i=1;i<=k;++i)
	  qwq[read()][read()]=1;
	for(int i=1;i<=n;++i)
	  for(int j=1;j<=m;++j)
	    if(!qwq[i][j]) add(i,n+j,1);
	for(int i=0;i<=t;++i)
	  if(f[i]<0) add(i,tt,-f[i]);
	  else add(ss,i,f[i]);
	add(t,0,inf),Dinic(ss,tt);
	for(int i=h[ss];i;i=c[i].x)
	  if(c[i].dis) return printf("JIONG!"),0;
	for(int i=h[tt];i;i=c[i].x)
	  if(c[i^1].dis) return printf("JIONG!"),0;
	return printf("%d",inf-Dinic(t,0)),0;
}

题目