C++11(clang++ 3.9) 解法, 执行用时: 12ms, 内存消耗: 1196K, 提交时间: 2020-10-08 16:39:36

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e4+5,M=5e5+5,Inf=1e9;
const int dx[]={1,0,-1,0},
		  dy[]={0,1,0,-1};
struct Edge{int to,f,nxt;}e[M];
int n,m,s,t,fst[N],nf[N],tote,q[N],hd,tl,lev[N];
void adde(int u,int v,int f){
	e[++tote]=(Edge){v,f,fst[u]};fst[u]=tote;
	e[++tote]=(Edge){u,0,fst[v]};fst[v]=tote;
}
bool bfs(){
	memset(lev,-1,sizeof(lev));
	q[hd=tl=1]=s;lev[s]=0;
	while(hd<=tl){
		int u=q[hd++];
		for(int i=fst[u],v;~i;i=e[i].nxt)if(e[i].f&&lev[v=e[i].to]<0)
			lev[v]=lev[u]+1,q[++tl]=v;
	}
	return lev[t]>=0;
}
int dfs(int u,int lim){
	if(u==t)return lim;
	int res=0;
	for(int i=nf[u],v,f;~i;i=e[i].nxt){
		v=e[i].to;f=e[i].f;
		if(lev[v]==lev[u]+1&&f){
			int tmp=dfs(v,min(f,lim));
			e[i].f-=tmp;e[i^1].f+=tmp;lim-=tmp;res+=tmp;
			if(!lim){nf[u]=i;return res;}
		}
	}
	nf[u]=-1;return res;
}
int maxflow(){
	int res=0;
	while(bfs())memcpy(nf,fst,sizeof(nf)),res+=dfs(s,Inf);
	return res;
}
int a[105][105],id[105][105],dfn;
int main(){
	memset(fst,-1,sizeof(fst));tote=1;
	scanf("%d%d",&n,&m);
	s=n*m+1;t=n*m+2;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]),id[i][j]=++dfn;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
		if(a[i][j]==1)adde(s,id[i][j],Inf);
		else if(a[i][j]==2)adde(id[i][j],t,Inf);
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j]!=2){
		for(int k=0,x,y;k<4;k++){
			x=i+dx[k];y=j+dy[k];
			if(x>=1&&x<=n&&y>=1&&y<=m&&a[x][y]!=1)adde(id[i][j],id[x][y],1);
		}
	}
	printf("%d\n",maxflow());
	return 0;
}