about ISAP

ISAP（vector version）：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int p[1010], d[1010], qq[1010], qb[1010];
int w[1010], hsh[1005];
struct node{
    int v, c, id;
};
vector<node> G[1005];
int ans, mxf, ttmp;
int m, n, s, t, u, mn, hj;
bool fl;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= m; i++){
        int u, v, c, fl = 0;
        cin >> u >> v >> c;
        G[u].push_back({v, c, G[v].size()});
        G[v].push_back({u, 0, G[u].size() - 1});
    }
    hsh[0] = n;
    for (int i = 1; i <= n; i++)
        p[i] = 1;
    u = s;
    mxf = INT_MAX;
    while (d[s] < n){
        w[u] = mxf;
        fl = 0;
        for (int i = 0; i < G[u].size(); i++){
            auto tmp = G[u][i];
            int v = tmp.v, c = tmp.c, id = tmp.id;
        //  if (v < p[u])
        //      continue;
            if (c > 0 && d[u] == d[v] + 1){
                fl = 1;
                p[u] = v;
                if (c < mxf)
                    mxf = c;
                qq[v] = u;
                qb[v] = i;
                u = v;
                if (u == t){
                    ans += mxf;
                    while (u != s){
                        ttmp = u;
                        u = qq[u];
                        G[u][qb[ttmp]].c -= mxf;
                        G[ttmp][G[u][qb[ttmp]].id].c += mxf;
                    }
                    mxf = LLONG_MAX;
                }
                break;
            }
        }
        if (fl)
            continue;
        mn = n - 1;
        for (auto tmp : G[u])
            if (tmp.c && d[tmp.v] < mn)
                hj = tmp.v, mn = d[tmp.v];
        p[u] = hj;
        hsh[d[u]]--;
        if (!hsh[d[u]])
            break;
        d[u] = mn + 1;
        hsh[d[u]]++;
        if (u != s){
            u = qq[u];
            mxf = w[u];
        }
    }
    cout << ans;
}

ISAP：（adjacency matrix version）

#include<bits/stdc++.h>
#define int long long
using namespace std;
int p[1010], d[1010], qq[1010];
int w[1010], hsh[1005];
int G[1005][1005];
int ans, mxf, tmp;
int m, n, s, t, u, mn, hj;
bool fl;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= m; i++){
        int u, v, c;
        cin >> u >> v >> c;
        G[u][v] += c;
    }
    hsh[0] = n;
    for (int i = 1; i <= n; i++)
        p[i] = 1;
    u = s;
    mxf = INT_MAX;
    while (d[s] < n){
        w[u] = mxf;
        fl = 0;
        for (int v = p[u]; v <= n; v++){
            if (G[u][v] > 0 && d[u] == d[v] + 1){
                fl = 1;
                p[u] = v;
                if (G[u][v] < mxf)
                    mxf = G[u][v];
                qq[v] = u;
                u = v;
                if (u == t){
                    ans += mxf;
                    while (u != s){
                        tmp = u;
                        u = qq[u];
                        G[u][tmp] -= mxf;
                        G[tmp][u] += mxf;
                    }
                    mxf = INT_MAX;
                }
                break;
            }
        }
        if (fl)
            continue;
        mn = n - 1;
        for (int j = 1; j <= n; j++)
            if (G[u][j] && d[j] < mn)
                hj = j, mn = d[j];
        p[u] = hj;
        hsh[d[u]]--;
        if (!hsh[d[u]])
            break;
        d[u] = mn + 1;
        hsh[d[u]]++;
        if (u != s){
            u = qq[u];
            mxf = w[u];
        }
    }
    cout << ans;
}

为什么删掉 if (v < p[u])continue; 就能过，不删 76？