*【二分图：最大独立集（难度：5）】骑士放置
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Description
【题意】0x60图论（0x69 二分图的覆盖与独立集）例题3：骑士放置(负责人：李羽山)ok给定一个 N*M 的棋盘，有一些格子禁止放棋子。
问棋盘上最多能放多少个不能互相攻击的骑士（国际象棋的“骑士”，类似于中国象棋的“马”，按照“日”字攻击，但没有中国象棋“别马腿”的规则）。
【输入格式】
第一行包含三个整数N,M,T，其中T表示禁止放置的格子的数量（1≤N,M≤100）。
接下来T行每行包含两个整数x和y，表示位于第x行第y列的格子禁止放置，行列数从1开始。
【输出格式】
输出一个整数表示结果。
【输入样例】
2 3 0
【输出样例】
4
Hint
#include<bits/stdc++.h>
using namespace std;
int dx[8]={-2, -1, 1, 2, -2, -1, 1, 2};
int dy[8]={-1, -2, -2, -1, 1, 2, 2, 1};
struct edge{int x, y, pre;}a[210000];int alen, last[11000];
void ins(int x, int y) {a[++alen]={x, y, last[x]}; last[x]=alen;}
bool v[110][110];
int n, m, t, match[110000], chw[110000], tsp;
bool dfs(int x)
{
for(int k=last[x];k;k=a[k].pre)
{
int y=a[k].y;
if(chw[y]!=tsp)
{
chw[y]=tsp;
if(!match[y]||dfs(match[y]))
{
match[y]=x;
return True;
}
}
}
return False;
}
int main()
{
scanf("%d%d%d", &n, &m, &t);
memset(v,0,sizeof(v));
for(int i=1,x,y;i<=t;i++)scanf("%d%d",&x,&y),v[x][y]=1;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!v[i][j]&&(i+j)%2)
for(int k=0;k<8;k++)
{
int x=i+dx[k];
int y=j+dy[k];
if(x>0&&y>0&&x<=n&&y<=m&&!v[x][y])ins((i-1)*m+j, (x-1)*m+y);
}
int ans=0;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if((i+j)%2&&!v[i][j])
{
tsp++;
if(dfs((i-1)*m+j)) ans++;
}
printf("%d", n*m-t-ans);
return 0;
}
</p>