求助&&建议添加hack数据

本题在添加白色点到黑色点之间的边时，若只在白色点无障碍时添加，虽然能够通过本题数据，但会在如下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));
}

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