本题在添加白色点到黑色点之间的边时，若只在白色点无障碍时添加，虽然能够通过本题数据，但会在如下hack数据WA。 代码：

#include <bits/extc++.h>
#include <bits/stdc++.h>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
const int maxn = 40005;
long long a[205][205];
class A
{
public:
	int to;
	long long cap, flow;
	int r;//反向边的位置
};
vector<A> G[maxn];
int pre[maxn], preedge[maxn], d[maxn], num[maxn], cur[maxn];//d为与t的距离，num[i]为距离为i的点的数量,cur为当前弧
bitset<maxn> vis;
void addedge(int u, int v, int cap)//网络流的特殊建图
{
	G[u].push_back({v, cap, 0, (int) G[v].size()});
	G[v].push_back({u, 0, 0, (int) G[u].size() - 1});
}
long long add(int s, int t)//将当前轮次的贡献统计
{
	int now = t;
	long long a = 99999999999999;
	while (now != s)
	{
		auto &p = G[pre[now]][preedge[now]];
		a = min(a, p.cap - p.flow);
		now = pre[now];
	}
	now = t;
	while (now != s)
	{
		auto &p = G[pre[now]][preedge[now]];
		p.flow += a;
		G[p.to][p.r].flow -= a;
		now = pre[now];
	}
	return a;
}
long long ISAP(int s, int t, int n)//s为源点，t为汇点，n为边数，求最大流
{
	queue<int> q;//BFS对图分层
	q.push(t);
	vis[t] = 1;
	while (!q.empty())
	{
		int now = q.front();
		q.pop();
		for (auto i: G[now])
		{
			if (!vis[i.to] && G[i.to][i.r].cap)//找反向边有容量的
			{
				vis[i.to] = 1;
				d[i.to] = d[now] + 1;
				q.push(i.to);
			}
		}
	}
	for (int i = 0; i <= n; i++)
		num[d[i]]++;
	int now = s;
	long long flow = 0;
	while (d[s] < n)
	{
		if (now == t)
		{
			flow += add(s, t);
			now = s;
		}
		bool ok = false;
		for (int i = cur[now]; i < G[now].size(); i++)
		{
			auto &v = G[now][i];
			if (v.cap > v.flow && d[now] == d[v.to] + 1)
			{
				ok = true;
				pre[v.to] = now;
				preedge[v.to] = i;
				cur[now] = i;
				now = v.to;
				break;
			}
		}
		if (!ok)//没有成功传流
		{
			int m = n - 1;
			for (int i = 0; i < G[now].size(); i++)
			{
				auto &v = G[now][i];
				if (v.cap > v.flow)
					m = min(m, d[v.to]);
			}
			num[d[now]]--;
			if (!num[d[now]])
				break;
			d[now] = m + 1;//下降高度
			num[d[now]]++;
			cur[now] = 0;
			if (now != s)//回溯
				now = pre[now];
		}
	}
	return flow;
}
const int x[8] = {-2, -2, -1,-1,1,1,2,2,};
const int y[8] = {1, -1, 2,-2,2,-2, -1,1};
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m, u, v;
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++)
	{
		scanf("%d %d", &u, &v);
		a[u][v] = 1;
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
		{
			if (!a[i][j])
			{
				if ((i + j) % 2)
				{
					addedge(0, (i - 1) * n + j, 1);
					for (int k = 0; k < 8; k++)
						if (i + x[k] > 0 && i + x[k] <= n && j + y[k] > 0 && j + y[k] <= n)
							addedge((i - 1) * n + j, (i + x[k] - 1) * n + (j + y[k]), 1e18);
				}
				else
					addedge((i - 1) * n + j, n * n + 1, 1);
			}
		}
	printf("%lld", n*n-m- ISAP(0, n * n + 1, n * n + 2));
}

数据：

4 8
1 1
1 2
1 3
2 4
3 1
3 2
3 4
4 1

答案：

4

输出：

5

若改为“无论白色点是否有障碍，都要向黑色点连边，但只在黑色点无障碍时连边”可通过此数据。 代码：

#include <bits/extc++.h>
#include <bits/stdc++.h>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
const int maxn = 40005;
long long a[205][205];
class A
{
public:
	int to;
	long long cap, flow;
	int r;//反向边的位置
};
vector<A> G[maxn];
int pre[maxn], preedge[maxn], d[maxn], num[maxn], cur[maxn];//d为与t的距离，num[i]为距离为i的点的数量,cur为当前弧
bitset<maxn> vis;
void addedge(int u, int v, int cap)//网络流的特殊建图
{
	G[u].push_back({v, cap, 0, (int) G[v].size()});
	G[v].push_back({u, 0, 0, (int) G[u].size() - 1});
}
long long add(int s, int t)//将当前轮次的贡献统计
{
	int now = t;
	long long a = 99999999999999;
	while (now != s)
	{
		auto &p = G[pre[now]][preedge[now]];
		a = min(a, p.cap - p.flow);
		now = pre[now];
	}
	now = t;
	while (now != s)
	{
		auto &p = G[pre[now]][preedge[now]];
		p.flow += a;
		G[p.to][p.r].flow -= a;
		now = pre[now];
	}
	return a;
}
long long ISAP(int s, int t, int n)//s为源点，t为汇点，n为边数，求最大流
{
	queue<int> q;//BFS对图分层
	q.push(t);
	vis[t] = 1;
	while (!q.empty())
	{
		int now = q.front();
		q.pop();
		for (auto i: G[now])
		{
			if (!vis[i.to] && G[i.to][i.r].cap)//找反向边有容量的
			{
				vis[i.to] = 1;
				d[i.to] = d[now] + 1;
				q.push(i.to);
			}
		}
	}
	for (int i = 0; i <= n; i++)
		num[d[i]]++;
	int now = s;
	long long flow = 0;
	while (d[s] < n)
	{
		if (now == t)
		{
			flow += add(s, t);
			now = s;
		}
		bool ok = false;
		for (int i = cur[now]; i < G[now].size(); i++)
		{
			auto &v = G[now][i];
			if (v.cap > v.flow && d[now] == d[v.to] + 1)
			{
				ok = true;
				pre[v.to] = now;
				preedge[v.to] = i;
				cur[now] = i;
				now = v.to;
				break;
			}
		}
		if (!ok)//没有成功传流
		{
			int m = n - 1;
			for (int i = 0; i < G[now].size(); i++)
			{
				auto &v = G[now][i];
				if (v.cap > v.flow)
					m = min(m, d[v.to]);
			}
			num[d[now]]--;
			if (!num[d[now]])
				break;
			d[now] = m + 1;//下降高度
			num[d[now]]++;
			cur[now] = 0;
			if (now != s)//回溯
				now = pre[now];
		}
	}
	return flow;
}
const int x[8] = {-2, -2, -1,-1,1,1,2,2,};
const int y[8] = {1, -1, 2,-2,2,-2, -1,1};
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m, u, v;
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++)
	{
		scanf("%d %d", &u, &v);
		a[u][v] = 1;
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
		{
			if((i+j)%2)
				for (int k = 0; k < 8; k++)
					if (i + x[k] > 0 && i + x[k] <= n && j + y[k] > 0 && j + y[k] <= n&&!a[i+x[k]][j+y[k]])
						addedge((i - 1) * n + j, (i + x[k] - 1) * n + (j + y[k]), 1e18);
			if (!a[i][j])
			{
				if ((i + j) % 2)
					addedge(0, (i - 1) * n + j, 1);
				else
					addedge((i - 1) * n + j, n * n + 1, 1);
			}
		}
	printf("%lld", n*n-m- ISAP(0, n * n + 1, n * n + 2));
}

这是为什么？感觉这两种应该是差不多的