洛谷 P3355 骑士共存问题

传送门 $\looparrowright$

题目描述

在一个 $n \times n$ 个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。

棋盘上某些方格设置了障碍，骑士不得进入。
对于给定的 $n \times n$ 个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑士，使得它们彼此互不攻击。

输入格式

第一行有 $2$ 个正整数 $n$ 和 $m$ ，分别表示棋盘的大小和障碍数。接下来的 $m$ 行给出障碍的位置。每行 $2$ 个正整数，表示障碍的方格坐标。

输出格式

将计算出的共存骑士数输出。

输入输出样例

输入 #1

3 2
1 1
3 3

输出 #1

5

说明/提示

对于全部的测试点，保证 $1 \leqslant n \leqslant 200$，$0 \leqslant m \lt n^2$ 。

分析

如下图所示。我们将所有点分成 $×$ 和 $√$ 两种点，可以发现同种点所在位置无法互相攻击。将所在行设为横坐标，所在列设为纵坐标，打叉的点坐标之和为偶数，打勾的点坐标之和为奇数；显然，只有坐标和奇偶性不同的两个位置才可能互相攻击。不妨建立二分图，设坐标和为偶数的方格为左部，坐标和为奇数的方格为右部。

二分图问题往往可以用网络流求解。建立超级源点 $s$ 和超级汇点 $t$，$s$ 向各个左部点连边，边权为 $1$；各个右部点向 $t$ 连边，边权为 $1$；$s$ 的出边和 $t$ 的入边都存在，代表一开始将所有没有障碍的位置放入骑士；若割去 $s$ 的一条入边，那么该边指向的节点所代表的方格就不会放置骑士。接着在左右两部节点之间建边，左部各个点向其互相冲突的至多八个右部点连边；这时，一定存在从 $s$ 到 $t$ 的路径，这条路径一定会包含一对互相冲突的节点，设为 $a,b$，意味着存在 $s$ 到 $a$ 的边和 $b$ 到 $t$ 的边，即两个冲突的位置同时放了骑士；我们的任务是割去一些 $s$ 的出边和 $t$ 的入边，使得 $s$ 和 $t$ 互不相通，且割去的边的边权要尽量小（删掉最少的非法骑士），这就联想到了最小割。将左右两部之间的边的边权设为 $+\infty$，该网络最小割即为要舍弃的骑士的数的总和，最初放置的 $n\times n-m$ 个骑士减去舍弃的骑士数量即为答案。需要注意的是，有一些位置本身就设置了不能放骑士，建图时这些点不能有任何连边。
最后，最大流等于最小割，建完图跑一遍 $\text{Dinic}$ 算法即可。

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 洛谷 P3355
Date: 7/28/2020
Description: Minimum Cut
*******************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAX_POINT=40023;
const int MAX_EDGE=400024;
const int MAX_POS=206;
const int inf=0x3f3f3f3f;
//8个骑士可以攻击的位置
const int dx[]={-2,-2,-1,-1,1,1,2,2};
const int dy[]={-1,1,-2,2,-2,2,-1,1};
bool forbidden[MAX_POS][MAX_POS];
struct E
{
	int to;
	int cap;
	int Next=-1;
}edge[MAX_EDGE];
int head[MAX_POINT],tot;
int s,t;
int depth[MAX_POINT];
int n,m;
void init();
inline void add_edge(int,int,int);
inline int ID(int,int);
bool bfs();
int dfs(int,int);
int Dinic();
int main()
{
	int i,j,k;
	cin>>n>>m;
	int sum=n*n-m;//所有可行位置放上骑士
	init();
	for(i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		forbidden[x][y]=1;
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(forbidden[i][j]) continue;
			if((i+j)&1) add_edge(ID(i,j),t,1);//右部
			else//左部
			{
				add_edge(s,ID(i,j),1);
				for(k=0;k<8;k++)
				{
					int x=i+dx[k];//行
					int y=j+dy[k];//列
					if(x<1||x>n||y<1||y>n) continue;
					if(forbidden[x][y]) continue;
					add_edge(ID(i,j),ID(x,y),inf);
				}
			}
		}
	}
	cout<<sum-Dinic()<<endl;
	return 0;
}
void init()
{
	tot=1;
	memset(head,-1,sizeof(head));
	s=0;
	t=n*n+1;
}
inline int ID(int x,int y) {return (x-1)*n+y;}
inline void add_edge(int u,int v,int cap)
{
	tot++;
	edge[tot].to=v;
	edge[tot].cap=cap;
	edge[tot].Next=head[u];
	head[u]=tot;
	//建立反边
	tot++;
	edge[tot].to=u;
	edge[tot].cap=0;
	edge[tot].Next=head[v];
	head[v]=tot;
}
bool bfs()
{
	memset(depth,0,sizeof(depth));
	queue<int>q;
	q.push(s);
	depth[s]=1;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(register int i=head[x];~i;i=edge[i].Next)
		{
			int y=edge[i].to;
			//残量网络上构建分层图
			if(edge[i].cap&&!depth[y])
			{
				q.push(y);
				depth[y]=depth[x]+1;
				if(y==t) return 1;//汇点可达
			}
		}
	}
	return 0;
}
int dfs(int x,int flow)//当前节点 当前流量
{
	//dfs 返回残量网络上可增广的流量
	if(x==t) return flow;
	int rest=flow;//rest 剩余流量
	int temp;
	for(register int i=head[x];~i&&rest;i=edge[i].Next)
	{
		int y=edge[i].to;
		if(edge[i].cap&&depth[y]==depth[x]+1)
		{
			temp=dfs(y,min(rest,edge[i].cap));
			if(!temp) depth[y]=0;//剪枝 去掉增广完毕的点
			edge[i].cap-=temp;
			edge[i^1].cap+=temp;
			rest-=temp;
		}
	}
	return flow-rest;
}
int Dinic()
{
	int maxflow=0;
	while(bfs()) maxflow+=dfs(s,inf);
	return maxflow;
}