BZOJ4808: 马

BZOJ4808: 马

https://lydsy.com/JudgeOnline/problem.php?id=4808

分析:

• 黑白染色，求二分图最大匹配即可。

代码:

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cstdlib>

#include <set>

#include <vector>

#include <cmath>

using namespace std;

#define N 40050

#define M 500050

#define inf 0x3f3f3f3f

const int S=N-1,T=N-2;

int head[N],to[M],nxt[M],flow[M],cnt=1,n,m;

int Q[N],dep[N];

inline void add(int u,int v,int f) {

	to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; flow[cnt]=f;

	to[++cnt]=u; nxt[cnt]=head[v]; head[v]=cnt; flow[cnt]=0;

}

bool bfs() {

	memset(dep,0,sizeof(dep));

	int l=0,r=0;

	Q[r++]=S; dep[S]=1;

	while(l<r) {

		int x=Q[l++],i;

		for(i=head[x];i;i=nxt[i]) if(!dep[to[i]]&&flow[i]) {

			dep[to[i]]=dep[x]+1; if(to[i]==T) return 1; Q[r++]=to[i];

		}

	}return 0;

}

int dfs(int x,int mf) {

	int i,nf=0;

	if(x==T) return mf;

	for(i=head[x];i;i=nxt[i]) if(dep[to[i]]==dep[x]+1&&flow[i]) {

		int tmp=dfs(to[i],min(mf-nf,flow[i]));

		if(!tmp) dep[to[i]]=0;

		nf+=tmp; flow[i]-=tmp; flow[i^1]+=tmp;

		if(nf==mf) break;

	}

	return nf;

}

int dinic() {

	int mxf=0,f=0;

	while(bfs()) {

		while((f=dfs(S,inf))) mxf+=f;

	}

	return mxf;

}

int idx[205][205],c[205][205];

int tx[]={-2,-1,1,2,2,1,-1,-2};

int ty[]={1,2,2,1,-1,-2,-2,-1};

int main() {

	scanf("%d%d",&n,&m);

	int i,j,k;

	for(i=1;i<=n;i++) {

		for(j=1;j<=m;j++) {

			idx[i][j]=++idx[0][0];

			c[i][j]=(i+j)&1;

		}

	}

	int x,ans=0;

	for(i=1;i<=n;i++) for(j=1;j<=m;j++) {

		scanf("%d",&x);

		if(!x) {

			if(!c[i][j]) add(S,idx[i][j],1);

			else add(idx[i][j],T,1);

			ans++;

		}

	}

	for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(!c[i][j]) {

		int x=i,y=j;

		for(k=0;k<8;k++) {

			int dx=x+tx[k], dy=y+ty[k];

			if(dx>=1&&dx<=n&&dy>=1&&dy<=m) {

				add(idx[x][y],idx[dx][dy],1);

			}

		}

	}

	ans-=dinic();

	printf("%d\n",ans);

}