洛谷原题
CodeVS 原题
题目描述
在一个 $n*n$ 个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍，骑士不得进入。
对于给定的 $n*n$ 个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑士，使得它们彼此互不攻击。
输入格式
第一行有 2 个正整数n 和 m (1<=n<=100)，分别表示棋盘的大小和障碍数。接下来的 m 行给出障碍的位置。每行 2 个正整数，表示障碍的方格坐标。
输出格式
将计算出的共存骑士数输出。
思路
看图。
选了黄色的相应的红色块就不能选。
在这样的点对之间连边得到二分图。
最多能放置的骑士就是这张二分图的最小顶点覆盖。
网络流跑一遍即可（实际上匈牙利也是可以的，最小顶点覆盖等于二分图的最大匹配，证明）。
代码
#include
#define inf 1e9
#define maxn 400000
#define id(i,j) ((i-1)*n+j)
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct Edge{
int to,next,val;
Edge(int a=0,int b=0,int c=0){
to=a,next=b,val=c;
}
}l[maxn];
int head[maxn],s,t,n,m,cnt=1,deep[maxn];
int cur[maxn],maxflow,ava[202][202];
int dx[8]={1,1,2,2,-1,-1,-2,-2};
int dy[8]={2,-2,-1,1,-2,2,1,-1};
void add(int a,int b,int c){
l[++cnt]=Edge(b,head[a],c);
head[a]=cnt;
}
bool bfs(){
memset(deep,0x7f,sizeof(deep));
queueq;
q.push(s);deep[s]=0;
for (int i=0;i<=n*n+1;i++) cur[i]=head[i];
while(!q.empty()){
int hq=q.front();q.pop();
for (int i=head[hq];i;i=l[i].next){
int v=l[i].to;
if (deep[v]>inf&&l[i].val)
deep[v]=deep[hq]+1,q.push(v);
}
}
return deep[t]n||ny<1||ny>n||ava[nx][ny]) continue;
add(id(i,j),id(nx,ny),inf),add(id(nx,ny),id(i,j),0);
}
}
else{
add(t,id(i,j),0);
add(id(i,j),t,1);
}
}
}
dinic();
cout<