本文共 1732 字，大约阅读时间需要 5 分钟。

问题可以抽象为图上选择最多的点,使得任意两个点间没有边

很明显的最大独立集

最大独立集=点数-最大匹配

所以这里需要抽象为二分图求最大匹配,发现按照马走日的走法,知道的点一定是性质不同的点

这个性质不同就是横坐标+纵坐标的奇偶性质

由奇数点连向偶数点构造二分图即可

#include 
   
    using namespace std;const int maxn=5e6+10;const int inf=1e9;struct edge{
   	int to,nxt,flow;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v,int flow){
   	d[++cnt]=(edge){
   v,head[u],flow},head[u]=cnt;	d[++cnt]=(edge){
   u,head[v],0},head[v]=cnt;}int dis[maxn],n,s,t,ans;char a[1009][1009];bool bfs(int s,int  t){
   	queue
    
     q;	for(int i=0;i<=t;i++)	dis[i]=0;	dis[s]=1;  q.push( s );	while( !q.empty() )	{
   		int u=q.front(); q.pop();		for(int i=head[u];i;i=d[i].nxt )		{
   			int v=d[i].to;			if( dis[v]==0&&d[i].flow )			{
   				dis[v]=dis[u]+1;	q.push(v);				if( v==t )	return true;			}		}	}	return false;}int dinic(int u,int flow){
   	if( u==t )	return flow;	int res=flow;	for(int i=head[u]; i&&res ;i=d[i].nxt )	{
   		int v=d[i].to;		if( d[i].flow&&dis[v]==dis[u]+1 )		{
   			int temp=dinic(v,min(res,d[i].flow) );			if( temp==0 )	dis[v]=0;			d[i].flow-=temp; d[i^1].flow+=temp;			res-=temp;		}	}	return flow-res;}int fx[10] = {
   1,1,2,2,-1,-1,-2,-2};int fy[10] = {
   -2,2,-1,1,-2,2,-1,1};int id(int x,int y){
   	return (x-1)*n+y;}int main(){
   	cin >> n;	for(int i=1;i<=n;i++)	cin >> ( a[i]+1 );	s = 0, t = n*n*2+1;	for(int i=1;i<=n;i++)	for(int j=1;j<=n;j++)	{
   		if( a[i][j]=='0' )	ans++;		if( a[i][j]=='1' )	continue;		if( (i+j)&1 )	add( id(i,j)+n*n,t,1 );		else		{
   			add( s,id(i,j),1 );			for(int w=0;w<=7;w++)			{
   				int nx = i+fx[w], ny = j+fy[w];				if( nx<1 || nx> n || ny < 1 || ny > n )	continue;				if( a[nx][ny] == '1' )	continue;				add( id(i,j),id(nx,ny)+n*n,1 );			}		}	}	while( bfs(s,t) )	ans -= dinic(s,inf);	cout << ans;}
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/115370595 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！