跑了甚至有 640ms。

记录

#include <bits/stdc++.h>
#include <iostream>
using namespace std;

int n, m, s, t;

struct Dinic {
    struct line {
        int to;
        long long w;
        int fb;
        bool vis = false;
    };

    int n, s, t;
    long long mx = 0;
    bool vis;
    vector<vector<line>> mp;
    vector<long long> dep;
    vector<bool> inq;

    Dinic(int _n, int _s, int _t) : n(_n), s(_s), t(_t) {
        mp.resize(n + 10, {});
    }

    Dinic() {}

    void add(int u, int v, long long w) {
        mp[v].push_back({u, 0, int(mp[u].size())});
        mp[u].push_back({v, w, int(mp[v].size() - 1)});
    }

    bool fc() {
        dep.clear();
        inq.clear();
        dep.resize(n + 10, 1e9);
        inq.resize(n + 10, false);
        queue<int> q;

        dep[s] = 0;
        q.push(s);

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            inq[u] = false;

            for (auto &i : mp[u]) {
                if (dep[i.to] > dep[u] + 1 && i.w > 0) {
                    dep[i.to] = dep[u] + 1;
                    if (!inq[i.to]) {
                        q.push(i.to);
                        i.vis     = false;
                        inq[i.to] = true;
                    }
                }
            }
        }

        return !(dep[t] == 1e9);
    }

    long long dfs(int u, long long flow) {
        long long ans = 0, used = 0;
        if (u == t) {
            vis = true;
            mx += flow;
            return flow;
        }

        for (int i = 0; i < mp[u].size(); i++) {
            int v = mp[u][i].to;

            if (mp[u][i].w > 0 && dep[v] == dep[u] + 1 && !mp[u][i].vis) {
                mp[u][i].vis = true;
                if ((ans = dfs(v, min(flow - used, mp[u][i].w)))) {
                    used += ans;
                    mp[u][i].w -= ans;
                    mp[mp[u][i].to][mp[u][i].fb].w += ans;
                    if (used == flow) {
                        break;
                    }
                }
            }
        }

        return used;
    }

    long long work() {
        while (fc()) {
            vis = true;
            while (vis) {
                vis = false;
                dfs(s, 1e9);
            }
        }
        return mx;
    }
} dinic;

int main() {

    // freopen("Dinic.in", "r", stdin);
    // freopen("Dinic.out", "w", stdout);

    cin >> n >> m >> s >> t;

    dinic = Dinic(n, s, t);

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        dinic.add(u, v, w);
    }

    cout << dinic.work();

    // fclose(stdin);
    // fclose(stdout);

    // system("pause");

    return 0;
}