提供一组 ISAP 的 hack

P3376 【模板】网络最大流

panhongxuanyyds @ 2023-03-29 22:17:50

hack 数据：

\texttt{input:}

7 8 1 7
1 2 1
1 3 1
2 4 1
3 4 1
4 7 1
4 5 1
5 7 1
4 6 2147483647

\texttt{output:}

\texttt{wrong output:}

这个 hack 数据能 hack 掉每次通过寻找出边中深度的最小值并更新该点的深度，且汇点的深度初始设为 0 ，且没有判该点能否走到汇点的写法，如我的提交记录。但是题解里面都写的是给该点的深度加 1 的写法，所以 hack 不掉题解……

hack 的原理：第一次，从 1 出发沿着 1 \rightarrow 3 \rightarrow 4 和 1 \rightarrow 2 \rightarrow 4 中的一条路径走到 4，并给 7 传输 1 的流量。此时该点流量已经用完，于是更新深度，6 号点的深度为 -1，于是把 4 号点的深度更新为 -1 + 1 = 0。

第二次，从 1 出发沿着 1 \rightarrow 3 \rightarrow 4 和 1 \rightarrow 2 \rightarrow 4 中的另一条路径走到 4，由于 4 号点的深度为 0，7 号点的深度为 0，5 号点的深度为 1，所以只能向 6 号点传输 1 的流量，但是 6 号点无法到达汇点，不会计入答案。

综上，我的程序会输出 1，但是正确答案是 2。

解决方法很简单，要么使用每次将深度加 1 的写法，要么判断一下，禁止跑到无法到达汇点的点即可。

申请管理员将该 hack 数据加入测试数据。

为方便大家，把代码放到二楼。

by panhongxuanyyds @ 2023-03-29 22:22:51

上面那个链接放错了，重新放一下：我的提交记录

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 400, maxm = 20000;
const ll N = maxn * 2 + 10, M = maxm + 10;
const ll INF = 0x3f3f3f3f3f3f3fll;
ll n, m, num, s, t, S, ans, H[N], C[N], de[N], gp[N];
bool fl;
struct edg{
    ll t, nxt, len;
}E[M * 2];
void add_edg(ll x, ll y, ll w) {
    ++num;
    E[num].t = y;
    E[num].nxt = H[x];
    E[num].len = w;
    H[x] = num;
}
void add_edges(ll x, ll y, ll w) {
    add_edg(x, y, w);
    add_edg(y, x, 0);
}
ll dfs(ll x, ll y) {
    if (x == t) {
        return y;
    }
    ll z = y, res = 0;
    for (ll i = C[x]; i > 0 && z > 0; i = E[i].nxt) {
        C[x] = i;
        ll v = E[i].t, w = E[i].len;
        if (w > 0 && de[v] + 1 == de[x]) {
            ll k = dfs(v, min(w, z));
            E[i].len -= k;
            E[(i ^ 1)].len += k;
            z -= k;
            res += k;
            if (z == 0) {
                return res;
            }
        }
    }
    --gp[de[x]];
    if (gp[de[x]] == 0) {
        fl = 0;
    }
    ll p = S;
    for (ll i = H[x]; i > 0; i = E[i].nxt) {
        ll v = E[i].t, w = E[i].len;
        if (w > 0) {
            p = min(p, de[v]);
        }
    }
    de[x] = p + 1;
    ++gp[de[x]];
    return res;
}
void bfs() {
    for (ll i = 1; i <= S; ++i) {
        de[i] = -1;
    }
    de[t] = 0;
    for (ll i = 1; i <= S; ++i) {
        gp[i] = 0;
    }
    queue<ll> q;
    q.push(t);
    while (!q.empty()) {
        ll x = q.front();
        q.pop();
        ++gp[de[x]];
        for (ll i = H[x]; i > 0; i = E[i].nxt) {
            ll v = E[i].t;
            if (i % 2 == 1 && de[v] == -1) {
                de[v] = de[x] + 1;
                q.push(v);
            }
        }
    }
}
void ISAP() {
    bfs();
    fl = 1;
    while (de[s] < S && fl) {
        for (ll i = 1; i <= S; ++i) {
            C[i] = H[i];
        }
        fl = 1;
        ll k = dfs(s, INF);
        ans += k;
    }
}
int main() {
    scanf("%lld%lld%lld%lld", &n, &m, &s, &t);
    num = 1;
    S = n;
    for (ll i = 1; i <= m; ++i) {
        ll u, v, w;
        scanf("%lld%lld%lld", &u, &v, &w);
        add_edges(u, v, w);
    }
    ISAP();
    printf("%lld", ans);
    return 0;
}

by assert_0 @ 2023-03-29 22:26:23

@dottle

by panhongxuanyyds @ 2023-03-31 21:51:35

又发现了一组 hack：

\texttt{input:}

8 9 6 7
6 1 2
1 3 2
3 8 2
8 7 2
1 2 2147483647
2 7 1
6 4 1
4 5 1
5 2 1

\texttt{output:}

\texttt{wrong output:}

by duckya @ 2024-01-11 17:26:08

太棒了！找到原因了！