自动搬运

查看原文

来自洛谷，原作者为

	w4p3r I think all our memories, and everything in it. . .can be nothing but the fiction we tell ourselves.

搬运于2025-08-24 21:48:03，当前版本为作者最后更新于2018-12-08 17:21:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言：

做这道题前可以先去做方格取数问题，那道题跟这道题区别不大，但是我觉得那道题比这道题更简单一点。

思路：

如果你已经做过了方格取数问题，那你会发现这道题所有点可以跟那道题一样分成两部分，而且分法一模一样，你可以自己画画图试试。

如果你没做过那道题，那也没事，我们先来看一个5x5的棋盘

如果我们将所有点分成O和X两种点，我们可以发现同种点无法互相攻击，而且如果你自己画图的话可以发现所有的图都有这个规律。

那我们可以把所有点分成两个点集，分别为O点的点集和X的点集，然后在两个点集有某些点对无法全选。

做法：

按照常规套路，先创一个源点和汇点

让源点到所有O点（即横纵坐标加起来为奇数的点）连一条容量为$1$的边

让所有X点（即横纵坐标加起来为偶数的点）到汇点连一条容量为$1$的边

再对无法同时选择的O点和X点，让O点连一条到X点容量为$inf$的点

当然，以上都是不考虑有障碍的点的

最后跑最大流，设为最大流为x，输出$n*n-m-x$就好了

证明：

为什么这样是正确的？

我们先简化模型，原题经我们分析相当于有一个二分图（设这两个点集分别为X，Y），我们要在这个二分图选出最多的点，使这些点中任意两个点之间没有边。

而我们要证明的即为，选出最多的点数=原点数-网络最大流

又最大流最小割定理，网络最大流=将源点汇点分开最小割的容量

所以我们将证明转换为了，选出最多点数=原点数-最小割

而我们知道，一个割就是将所有点分割成S和T两个集合，其中s∈S，t∈T

我们不妨假设S∪X即是我们在X中选的点，T∪Y即是我们在Y中选的点

显而易见的，S∪Y即是我们在X中不选的点，T∪X即是我们在Y中不选的点

那我们建inf的边意义即在我们强制了不能同时选的两点必在同一个集合（即为一个不选一个选），因为如果它们不在同一个集合中，割的大小就超过了inf，肯定不会成为最小割

而我们建1的边的意义即在如果X中的点不在S中，或者Y中的点不在T中，就会损失一个点，而损失当然越小越好了

所以可以得到选出最多点数=原点数-最小割,而又由最大流最小割定理，最小割=最大流，就可以跑最大流了。证毕。

这也就是二分图的最大独立集

本人只是一个提高370的菜鸡，证明可能严重稍微不大严谨，大家理解就好啦，就不要纠结我不会用数学语言证明了qwq。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<deque>
#define inf 0x7fffffff/2
#define eps 1e-6
#define N 100010
#define M 3000010
#define K 1010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
	char ch=getchar();
	ll s=0,w=1;
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
	return s*w;
}
struct edge
{
	int next,to,fl;
}e[M<<1];
int n,m;
int head[N],cnt=1;
int depth[N];
int x[8]={1,1,-1,-1,2,2,-2,-2},y[8]={2,-2,2,-2,1,-1,1,-1}; 
//马可以往8个方向跑
int flag[K][K];
queue<int>Q;
int s,t;
inline void add_edge(int from,int to,int fl)
{
	e[++cnt].to=to;
	e[cnt].next=head[from];
	e[cnt].fl=fl;
	head[from]=cnt;
}//加边
inline int arr(int x,int y)
{
	return (x-1)*n+y;
}//坐标转换
inline int bfs()
{
	memset(depth,0,sizeof(depth));while(!Q.empty())Q.pop();
	Q.push(s);depth[s]=1;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(register int i=head[x];i;i=e[i].next)
		{
			if(e[i].fl>0&&!depth[e[i].to])
			{
				depth[e[i].to]=depth[x]+1;Q.push(e[i].to);
			}
		}
	}
	return depth[t];
}
int dfs(int now,int flow)
{
	if(now==t)return flow;
	int ret=0;
	for(register int i=head[now];i;i=e[i].next)
	{
		if(ret==flow)return flow;
		if(depth[e[i].to]==depth[now]+1&&e[i].fl>0)
		{
			int fl=dfs(e[i].to,min(flow,e[i].fl));
			if(fl>0)
			{
				ret+=fl;
				e[i].fl-=fl;
				e[i^1].fl+=fl;
			}
		}
	}
	if(!ret)depth[now]=0;
	return ret;
}
inline int Dinic()
{
	int sum=0;
	while(bfs())
	{
		int x=1;while(x){x=dfs(s,inf);sum+=x;}
	}
	return sum;
}//最大流
int main()
{
	n=read(),m=read();
	t=n*n+1;//有n*n个点
	for(register int i=1;i<=m;i++)
	{
		int x=read(),y=read();
		flag[x][y]=1;
	}
	for(register int i=1;i<=n;i++)
	{
		for(register int j=1;j<=n;j++)
		{
			if((i+j)&1)
			{
				if(!flag[i][j]){add_edge(s,arr(i,j),1),add_edge(arr(i,j),s,0);}//O点
			}
			else
			{
				if(!flag[i][j]){add_edge(arr(i,j),t,1),add_edge(t,arr(i,j),0);}//X点
			}
		}
	}
	for(register int i=1;i<=n;i++)
	{
		for(register int j=1;j<=n;j++)
		{
			if(((i+j)&1)==0)continue;
			for(register int k=0;k<8;k++)
			{
				int tox=i+x[k],toy=j+y[k];
				if(tox>=1&&tox<=n&&toy>=1&&toy<=n&&!flag[tox][toy])
				{
					add_edge(arr(i,j),arr(tox,toy),inf),add_edge(arr(tox,toy),arr(i,j),0);
                    //对于不能同时选的点建inf边
				}
			}
		}
	}
	int flow=Dinic();//求出最小割即最大流
	printf("%d\n",n*n-m-flow);//输出
	return 0;
}

后记：

做了这道题我最大的启示就是马的路径居然可以和方格取数问题一样分成两类点，以后再遇到类似的棋盘中的问题时，要先看看棋盘中的点是否也能分成两种跑最大流。

如果你觉得我的题解写得还不错的话，希望你能给我点个赞。

如果你对我的题解有什么不懂的地方，或者我的题解写得有任何问题的话，可以私信我告知，我尽量将我的题解做到最好的程度。