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&lt;=n;i++)for(int j=1;j&lt;=m;j++)if(!v[i][j]&amp;&amp;(i+j)%2)
    for(int k=0;k&lt;8;k++)
    {
        int x=i+dx[k];
        int y=j+dy[k];
        if(x&gt;0&amp;&amp;y&gt;0&amp;&amp;x&lt;=n&amp;&amp;y&lt;=m&amp;&amp;!v[x][y])ins((i-1)*m+j&#44; (x-1)*m+y);
    }

int ans=0;
for(int i=1;i&lt;=n;i++)for(int j=1;j&lt;=m;j++)if((i+j)%2&amp;&amp;!v[i][j])
{
    tsp++;
    if(dfs((i-1)*m+j)) ans++;
}
printf("%d"&#44; n*m-t-ans);
return 0;

}

</p>