Dinic 609ms求且力

加了多路增广和当前弧优化，rest==0也判断了，为什么最大的点还是跑了609ms（

提交记录

#include <bits/stdc++.h>
#define int long long
#define Efor(xx, yy) for(int xx = Head[yy]; xx; xx = Next[xx])
#define Lfor(xx, yy, zz, xyz, ...) for(int xx = yy, ##__VA_ARGS__; xx <= zz; xx += xyz)
#define Rfor(xx, yy, zz, xyz, ...) for(int xx = yy, ##__VA_ARGS__; xx >= zz; xx -= xyz)
using namespace std;
struct FastIN
{
    char buf[(1 << 21) + 100], *p, *e;
    int getChar()
    {
        if (p == e) p = buf, e = buf + fread(buf, 1, (1 << 21), stdin);
        return p == e ? EOF : *p++;
    }
    template<typename T>
    FastIN& operator>>(T& x)
    {
        char c, l;
        for (c = 0; !isdigit(c); c = getChar()) l = c;
        for (x = 0; isdigit(c); c = getChar()) x = x * 10 - '0' + c;
        if (l == '-') x = -x;
        return *this;
    }
} IN;
const int kM = 1e4 + 14, kN = 2e2 + 22, INF = ~0ull >> 1;
int n, m, s, t;
struct Graph {
    int tot, Head[kN], Next[kM], Ver[kM], Edge[kM], Dep[kN], Now[kN];
    Graph() {
        tot = 1;
    }
    void Add(int, int, int);
    bool BFS();
    int Dinic(int, int);
} T;

signed main() {
#ifdef FIO
    freopen("D:/Code/In.in", "r", stdin);
    freopen("D:/Code/Out.out", "w", stdout);
#endif
    IN >> n >> m >> s >> t;
    Lfor (i, 1, m, 1, u, v, c) {
        IN >> u >> v >> c;
        T.Add(u, v, c), T.Add(v, u, 0);
    }
    int ans = 0, flow = 0;
    while (T.BFS()) while ((flow = T.Dinic(s, INF))) ans += flow;
    cout << ans;
    return 0;
}

void Graph::Add(int x, int y, int z) {
    Ver[++tot] = y, Edge[tot] = z, Next[tot] = Head[x], Head[x] = tot;
}

bool Graph::BFS() {
    queue <int> Q;
    Lfor (i, 0, n, 1) Now[i] = Head[i], Dep[i] = 0;
    Q.push(s), Dep[s] = 1;
    while (Q.size()) {
        int x = Q.front(); Q.pop();
        Efor (e, x) {
            int y = Ver[e];
            if (Edge[e] and !Dep[y]) {
                Q.push(y), Dep[y] = Dep[x] + 1;
                if (y == t) return 1;
            }
        }
    }
    return 0;
}

int Graph::Dinic(int x, int flow) {
    if (x == t) return flow;
    int rest = flow, e;
    for (e = Now[x]; e and rest; e = Next[e]) {
        int y = Ver[e];
        if (Edge[e] and Dep[y] == Dep[x] + 1) {
            int k = Dinic(y, min(rest, Edge[e]));
            if (!k) Dep[y] = 0;
            rest -= k, Edge[e] -= k, Edge[e ^ 1] += k;
        }
    }
    Now[x] = e;
    return flow - rest;
}