首页 > 代码库 > bzoj1458 士兵占领

bzoj1458 士兵占领

2024-08-03 22:47:26   215人阅读

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
 
 
预处理一下每行每列删完会不会爆，然后网络流搞出最多能删掉几个士兵
S向所有行连边，所有列向T连边，然后对于一个可行的点，它所在的行向它所在的列连边
这题建图真挺巧妙的
#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 0x7ffffff#define pa pair<int,int>#define pi 3.1415926535897932384626433832795028841971#define S 0#define T 20010using namespace std;inline LL read(){    LL x=0,f=1;char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}struct edge{	int to,next,v;}e[200010];int head[100010];int h[100010];int q[100010];int n,m,k,cnt=1,ans;int l[110],c[110],sl[110],sc[110];bool mrk[110][110];inline void ins(int u,int v,int w){	e[++cnt].to=v;	e[cnt].v=w;	e[cnt].next=head[u];	head[u]=cnt;}inline void insert(int u,int v,int w){	ins(u,v,w);	ins(v,u,w);}inline bool bfs(){	memset(h,-1,sizeof(h));	int t=0,w=1;	q[1]=S;h[S]=0;	while (t<w)	{		int now=q[++t];		for (int i=head[now];i;i=e[i].next)		  if (h[e[i].to]==-1&&e[i].v)		  {		  	h[e[i].to]=h[now]+1;		  	q[++w]=e[i].to;		  }	}	if (h[T]==-1)return 0;	return 1;}inline int dfs(int x,int f){	if (x==T||!f)return f;	int w,used=0;	for (int i=head[x];i;i=e[i].next)	  if (h[e[i].to]==h[x]+1&&e[i].v)	  {	  	w=dfs(e[i].to,min(e[i].v,f-used));	  	used+=w;	  	e[i].v-=w;	  	e[i^1].v+=w;	  	if (f==used)return used;	  }	if (!used)h[x]=-1;	return used;}inline void dinic(){	while (bfs())ans-=dfs(S,inf);}int main(){	n=read();m=read();k=read();	for (int i=1;i<=n;i++)l[i]=m-read();	for (int i=1;i<=m;i++)c[i]=n-read();	for (int i=1;i<=k;i++)	{		int x=read(),y=read();		mrk[x][y]=1;		sl[x]++;sc[y]++;		if (sl[x]>l[x]||sc[y]>c[y])		{			printf("JIONG!\n");			return 0;		}	}	ans=n*m-k;	for (int i=1;i<=n;i++) insert(S,i,l[i]-sl[i]);	for (int j=1;j<=m;j++) insert(n+j,T,c[j]-sc[j]);	for (int i=1;i<=n;i++)	  for (int j=1;j<=m;j++)	    if (!mrk[i][j])insert(i,n+j,1);	dinic();	printf("%d\n",ans);	return 0;}

 

bzoj1458 士兵占领


联系
我们