题意简述
给定一个 \(n\times n\) 的棋盘，有一些点不能放置棋子。问最多放多少个马，能让这些马互不攻击？
\(1 \leq n \leq 200\) 。
Solution
下面的棋盘的下表从 \(1\) 开始。
如果把两个可以放置棋子并且可以互相攻击的点连接，那么就会形成一个无向图，放最多的马就相当于求这张图的最大权独立集。
然后就是这种棋盘上放置马的常见套路了：如果把这张图二染色（对于格点 \((x,y)\) ，若 \(x+y\) 是奇数就染成白色，否则染成黑色），可以发现连接的点颜色都不相同（因为 \((x,y)\) 连接的点的坐标和的奇偶性会改变，读者可以模拟试一试），也就是说，这是张二分图。
根据二分图的性质，最大权独立集 = 总点数 - 最小点覆盖数，于是可以用匈牙利算法求解。
但是这题感觉这算法明显会超时，于是可以用网络流来求最小点覆盖数，建图的话：
- 如果一个点不能放置棋子，这个点不向任何点连边，也不让任何其他的点向这个点连边。
- 若一个点被染成了白色，从源点向这个点连接一条容量为 \(1\) 的边，同时从这个点向所有能能攻击的点连一条容量为 \(\infty\) 的边。
- 若一个点被染成了黑色，从这个点向汇点连一条容量为 \(1\) 的边。
最后答案 = 总点数（除去不能放置棋子的点） - 最小点覆盖 = 总点数 - 最小割 = 总点数 - 最大流。
于是问题就解决了，代码如下：
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <queue>
using namespace std;
inline int read() {
int num = 0 ,f = 1; char c = getchar();
while (!isdigit(c)) f = c == '-' ? -1 : f ,c = getchar();
while (isdigit(c)) num = (num << 1) + (num << 3) + (c ^ 48) ,c = getchar();
return num * f;
}
const int N = 4e4 + 5 ,M = 4e5 + 5 ,INF = 0x3f3f3f3f;
struct Edge {
int to ,w ,next;
Edge (int to = 0 ,int w = 0 ,int next = 0) : to(to) ,w(w) ,next(next) {}
}G[M]; int head[N] ,idx;
inline void add(int u ,int v ,int w) {
G[++idx] = Edge(v ,w ,head[u]); head[u] = idx;
G[++idx] = Edge(u ,0 ,head[v]); head[v] = idx;
}
namespace ISAP {
int n ,s ,t ,cur[N] ,dep[N] ,gap[N];
inline void bfs() {
memset(dep ,0 ,sizeof(dep));
memset(gap ,0 ,sizeof(gap));
queue <int> q;
dep[t] = 1; gap[1] = 1; q.push(t);
while (!q.empty()) {
int now = q.front(); q.pop();
for (int i = head[now]; i ; i = G[i].next) {
int v = G[i].to;
if (!dep[v]) {
dep[v] = dep[now] + 1;
gap[dep[v]]++;
q.push(v);
}
}
}
}
inline int ISAP(int now ,int flow) {
if (now == t) return flow;
int rest = 0;
for (int i = cur[now]; i ; i = G[i].next) {
cur[now] = i;
int v = G[i].to ,w = G[i].w;
if (dep[now] == dep[v] + 1 && w) {
int k = ISAP(v ,min(flow - rest ,w));
G[i].w -= k ,G[i ^ 1].w += k ,rest += k;
if (flow == rest) return flow;
}
}
gap[dep[now]]--;
if (gap[dep[now]] == 0) dep[s] = n + 1;
dep[now]++;
gap[dep[now]]++;
return rest;
}
inline int ISAP() {
int flow = 0;
bfs();
while (dep[s] <= n) {
for (int i = 1; i <= n; i++) cur[i] = head[i];
flow += ISAP(s ,INF);
}
return flow;
}
}
bool vis[205][205];
char s[205];
const int dx[] = {0 ,-2 ,-2 ,-1 ,-1 ,1 ,1 ,2 ,2} ,dy[] = {0 ,-1 ,1 ,-2 ,2 ,-2 ,2 ,-1 ,1};
int n ,sum;
inline int num(int x ,int y) {
return (x - 1) * n + y;
}
signed main() {
idx = 1;
n = read();
ISAP::n = n * n; ISAP::s = ISAP::n + 1 ;ISAP::t = ISAP::s + 1;
ISAP::n += 2;
for (int i = 1; i <= n; i++) {
scanf("%s" ,s + 1);
for (int j = 1; j <= n; j++)
if (s[j] == '1') vis[i][j] = true;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (!vis[i][j]) {
if (((i + j) & 1) == 0) {
add(ISAP::s ,num(i ,j) ,1);
for (int k = 1; k <= 8; k++) {
int tx = i + dx[k] ,ty = j + dy[k];
if (tx > 0 && ty > 0 && tx <= n && ty <= n && !vis[tx][ty])
add(num(i ,j) ,num(tx ,ty) ,INF);
}
}
else add(num(i ,j) ,ISAP::t ,1);
sum++;
}
printf("%d\n" ,sum - ISAP::ISAP());
return 0;
}