Thuật toán Tidal Flow tìm luồng cực đại

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

typedef long long ll;

const int MAXN = 1205;
const int MAXM = 120005;
const ll INF = 1e18;

struct edge {
    int to, rev;  // node, index in the other adjacency list
    ll cap;       // residual capacity
};

vector<edge> adjList[MAXN];  // adjacency list of the edges
int Ev[MAXM], Ei[MAXM];      // BFS edge list
int N, M, bfsPtr;            // number of nodes
int dist[MAXN], ok[MAXN];

ll h[MAXN];  // heuristic of Tidal Flow
ll p[MAXM];  // promised flow of Tidal Flow
ll l[MAXN];  // amount of flow in pool of Tidal FLow
int source, sink;
ll TidalFlow(int edgeListSize) {
    fill(h, h + N + 1, 0);  // initializing h[v], for all v
    h[source] = INF;        // there is no bound in the flow that can reach the source

    for (int i = 0; i < edgeListSize; i++) {
        int w = Ev[i];               // where it comes from
        int idx = Ei[i];             // index in the adjList
        int v = adjList[w][idx].to;  // where it goes
        p[i] =
            min(adjList[w][idx].cap, h[w]);  // the promised is the minimum of the heuristic and the capacity
        h[v] += p[i];                        // we add the promised capacity to the heuristic
    }

    if (h[sink] == 0)
        return 0;  // if the heuristic for the sink is 0, then we are done

    fill(l, l + N + 1, 0);  // initializing l[v], for all v
    l[sink] = h[sink];      // the amount of flow is the heuristic in the sink, initially

    for (int i = edgeListSize - 1; i >= 0; i--) {
        int w = Ev[i];               // where it comes from
        int idx = Ei[i];             // index in the adjList
        int v = adjList[w][idx].to;  // where it goes
        // the promised is the minimum of the promised before, the diference between heuristic and available
        // of the start or the available of the end
        p[i] = min(p[i], min(h[w] - l[w], l[v]));
        l[v] -= p[i];
        l[w] += p[i];
    }

    fill(h, h + N + 1, 0);  // h[v] = 0, for all v
    h[source] = l[source];  // the amount of pool is the heuristic
    for (int i = 0; i < edgeListSize; i++) {
        int w = Ev[i];                      // where it comes from
        int idx = Ei[i];                    // index in the adjList
        int v = adjList[w][idx].to;         // where it goes
        int rev_idx = adjList[w][idx].rev;  // index in the other adjList
        p[i] = min(p[i], h[w]);
        h[w] -= p[i];
        h[v] += p[i];
        adjList[w][idx].cap -= p[i];      // we update the residual capacity
        adjList[v][rev_idx].cap += p[i];  // update reverse edje capacity
    }

    return h[sink];
}

int BFS() {
    bfsPtr = 0;
    fill(ok, ok + N + 1, 0);

    queue<int> bfs;
    bfs.push(source);
    ok[source] = 1;
    dist[source] = 0;

    while (!bfs.empty()) {
        int v = bfs.front();
        bfs.pop();

        for (int i = 0; i < adjList[v].size(); i++) {
            if (adjList[v][i].cap == 0)
                continue;
            int u = adjList[v][i].to;
            if (ok[u]) {
                if (dist[u] == dist[v] + 1) {
                    Ev[bfsPtr] = v;
                    Ei[bfsPtr] = i;
                    bfsPtr++;
                }
                continue;
            }
            ok[u] = 1;
            dist[u] = dist[v] + 1;
            bfs.push(u);
            Ev[bfsPtr] = v;
            Ei[bfsPtr] = i;
            bfsPtr++;
        }
    }

    return bfsPtr;
}

ll FordFulkerson() {
    ll flow = 0;

    while (true) {
        ll augmenting = TidalFlow(BFS());
        if (augmenting == 0)
            break;
        else
            flow += augmenting;
    }

    return flow;
}

void addEdge(int u, int v, int cap) {
    edge newedge;
    int uPtr = (int)adjList[u].size();
    int vPtr = (int)adjList[v].size();

    newedge.to = v;
    newedge.rev = vPtr;
    newedge.cap = cap;
    adjList[u].push_back(newedge);

    newedge.to = u;
    newedge.rev = uPtr;
    newedge.cap = cap;
    adjList[v].push_back(newedge);
}

int main() {
    scanf("%d %d %d %d", &N, &M, &source, &sink);

    for (int i = 1; i <= M; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        addEdge(u, v, w);
    }

    printf("%lld\n", FordFulkerson());

    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define nmax 1201
#define mmax 120001
#define oo 2147483647
struct edge {int u, v, c, f;} e[2 * mmax];
int n, m, s, t, fValue = 0, head[nmax], link[2 * mmax];
int h[nmax], l[nmax], p[2 * mmax], d[nmax], le[2 * mmax], lm;
void enter() {
    cin >> n >> m >> s >> t;
    for (int u, v, c, i = 1; i <= m; i++) {
        cin >> u >> v >> c;
        e[i] = {u, v, c, 0};
        e[i + m] = {v, u, 0, 0};
    }
    memset(head, 0, sizeof head);
    for (int i = 1; i <= 2 * m; i++) {
        link[i] = head[e[i].u];
        head[e[i].u] = i;
    }
}

bool BFS() {
    queue<int> q;
    q.push(s);
    memset(d, -1, sizeof d);
    d[s] = lm = 0;
    while (q.size()) {
        int u = q.front();
        q.pop();
        if (u == t) continue;
        for (int i = head[u]; i; i = link[i]) {
            int v = e[i].v, c = e[i].c, f = e[i].f;
            if (c <= f) continue;
            if (d[v] >= 0) {
                if (d[v] == d[u] + 1)
                    le[++lm] = i;
            } else {
                d[v] = d[u] + 1;
                q.push(v);
                le[++lm] = i;
            }
        }
    }
    return d[t] >= 0;

}

int TideCycle() {
    if (!BFS()) return 0;
    memset(h, 0, sizeof h);
    h[s] = oo;
    for (int j = 1; j <= lm; j++) {
        int i = le[j];
        p[i] = min(e[i].c - e[i].f, h[e[i].u]);
        h[e[i].v] += p[i];
    }
    if (!h[t]) return 0;
    memset(l, 0, sizeof l);
    l[t] = h[t];
    for (int j = lm; j >= 1; j--) {
        int i = le[j];
        p[i] = min(p[i], min(h[e[i].u] - l[e[i].u], l[e[i].v]));
        l[e[i].v] -= p[i];
        l[e[i].u] += p[i];
    }
    memset(h, 0, sizeof h);
    h[s] = l[s];
    for (int j = 1; j <= lm; j++) {
        int i = le[j];
        p[i] = min(p[i], h[e[i].u]);
        h[e[i].u] -= p[i];
        h[e[i].v] += p[i];
        e[i].f += p[i];
        e[i > m ? i - m : i + m].f -= p[i];
    }
    return h[t];
}

void TidalFlow() {
    while (TideCycle())
        fValue += h[t];
    cout << fValue << '\n';
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    enter();
    TidalFlow();
}