codevs 1022 覆盖

1022 覆盖

题目描述 Description

有一个N×M的单位方格中，其中有些方格是水塘，其他方格是陆地。如果要用1×2的矩阵区覆盖（覆盖过程不容许有任何部分重叠）这个陆地，那么最多可以覆盖多少陆地面积。

输入描述 Input Description

输入文件的第一行是两个整数N，M (1<=N，M<=100)，第二行为一个整数K( K<=50)，接下来的K行，每行两个整数X，Y表示K个水塘的行列位置。(1<=X<=N，1<=Y<=M)。

输出描述 Output Description

输出所覆盖的最大面积块（1×2面积算一块）。

样例输入 Sample Input

4 4

1 1

1 4

2 2

4 1

4 2

4 4

样例输出 Sample Output

题解：

(⊙v⊙)嗯，一个矩形覆盖相邻两个格子，如果交替染成黑白两色，那么矩形一定是覆盖在一个黑格子和一个白格子上的，那么就是要求最多的相邻黑白格子的匹配数，一个二分图匹配问题。

把相邻的点连边，并连向s/t，找最大流即可那个时候好像还不太懂怎么转化为二分图匹配，就很智障的每个点向相邻点连边，用vis数组记录，保证不重复连边。后来发现可以根据i+j的奇偶

判断格子[i][j]连向哪边。

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#define nn 10010
#define mm 50010
#define inf 2000000001
using namespace std;
int get()
{
	int ans=0,f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) {ans=ans*10+ch-'0';ch=getchar();}
	return ans*f;
}
int e=0,n,tt,fir[nn],nxt[mm],to[mm],flow[mm],q[nn],dep[nn];
bool il[nn],vis[nn];
void add(int a,int b,int c)
{
	nxt[++e]=fir[a];fir[a]=e;to[e]=b;flow[e]=c;
	nxt[++e]=fir[b];fir[b]=e;to[e]=a;flow[e]=0;
}
bool bfs()
{
	int h=1,t=1,o;
	q[1]=0;
	while(h<=t)
	  {
	  	o=q[h++];
	  	for(int i=fir[o];i;i=nxt[i])
	  	  if(flow[i]&&!dep[to[i]])
	  	    {
	  	    	dep[to[i]]=dep[o]+1;
	  	    	q[++t]=to[i];
			}
	  }
	if(dep[tt]) return 1;
	return 0;
}
int maxflow(int s,int f)
{
	if(!f||s==tt) return f;         //写成了return 0 
	int newflow,newans=0;
	for(int i=fir[s];i;i=nxt[i])
	  if(dep[to[i]]==dep[s]+1&&flow[i])
	    {
	    	newflow=maxflow(to[i],min(f,flow[i]));            //流量要和flow[i]取min 
	    	f-=newflow;
	    	flow[i]-=newflow;
	    	flow[i+1]+=newflow;
	    	newans+=newflow;
	    	if(!f) break;
		}
	return newans;
}
int main()
{
    n=get();
	int m=get(),k=get(),ans=0,x,y;
	tt=n*m+1;
	for(int i=1;i<=k;i++)
	  {
	  	x=get();y=get();
	  	il[(x-1)*m+y]=1;
	  }
	for(int i=1;i<=n*m;i++)
	  if(!vis[i]&&!il[i])
	  {
	  	if(i-m>0&&!il[i-m]) 
		  {add(i,i-m,1);vis[i-m]=1;}
	  	if(i+m<=n*m&&!il[i+m]) 
		  {add(i,i+m,1);vis[i+m]=1;}
		if(i+1<=n*m&&!il[i+1]) 
		  {add(i,i+1,1);vis[i+1]=1;}
		if(i-1>0&&!il[i-1]) 
		  {add(i,i-1,1);vis[i-1]=1;}
	  }
	for(int i=1;i<=n*m;i++)
	  if(!il[i]&&!vis[i])
	    add(0,i,1);
	  else if(!il[i])
	    add(i,tt,1);
	dep[0]=1;
	while(bfs())
	  {
	  	ans+=maxflow(0,inf);
	  	for(int i=1;i<=tt;i++)
	  	  dep[i]=0;
	  	dep[0]=1;
	  }
	printf("%d",ans);
	return 0;
}