洛谷原题

CodeVS 原题

题目描述

在一个 $n*n$ 个方格的国际象棋棋盘上,马(骑士)可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍,骑士不得进入。

对于给定的 $n*n$ 个方格的国际象棋棋盘和障碍标志,计算棋盘上最多可以放置多少个骑士,使得它们彼此互不攻击。

输入格式

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

输出格式

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

思路

看图。
选了黄色的相应的红色块就不能选。
在这样的点对之间连边得到二分图。
最多能放置的骑士就是这张二分图的最小顶点覆盖。
网络流跑一遍即可(实际上匈牙利也是可以的,最小顶点覆盖等于二分图的最大匹配,证明)。

代码