用C++写EK求最大流的代码

以下是使用Edmonds-Karp算法实现最大流的示例C代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAXN 1000      // 最大节点数
#define MAXM 1000000   // 最大边数

int n, m;     // n为节点数，m为边数
int s, t;     // 源节点和汇节点
int head[MAXN], nxt[MAXM], to[MAXM], cap[MAXM], cur[MAXN], cnt = 1;   // 邻接表表示边

void add_edge(int u, int v, int c) {
    nxt[++cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
    cap[cnt] = c;
}

void init() {
    memset(head, 0, sizeof(head));
    cnt = 1;
}

int bfs() {
    static int q[MAXN], dep[MAXN];
    int l = 0, r = 0;
    memset(dep, -1, sizeof(dep));
    q[r++] = s;
    dep[s] = 0;
    while (l < r) {
        int u = q[l++];
        for (int i = head[u]; i; i = nxt[i]) {
            int v = to[i];
            if (dep[v] == -1 && cap[i]) {
                dep[v] = dep[u] + 1;
                q[r++] = v;
            }
        }
    }
    return dep[t] != -1;
}

int dfs(int u, int flow) {
    if (u == t) return flow;
    for (int &i = cur[u]; i; i = nxt[i]) {
        int v = to[i];
        if (cap[i] && dep[v] == dep[u] + 1) {
            int f = dfs(v, fmin(flow, cap[i]));
            if (f) {
                cap[i] -= f;
                cap[i ^ 1] += f;
                return f;
            }
        }
    }
    return 0;
}

int dinic() {
    int max_flow = 0;
    while (bfs()) {
        memcpy(cur, head, sizeof(cur));
        int f;
        while (f = dfs(s, INT_MAX)) {
            max_flow += f;
        }
    }
    return max_flow;
}

int main() {
    scanf("%d %d %d %d", &n, &m, &s, &t);
    init();
    for (int i = 1; i <= m; i++) {
        int u, v, c;
        scanf("%d %d %d", &u, &v, &c);
        add_edge(u, v, c);
        add_edge(v, u, 0);  // 反向边初始容量为0
    }
    printf("%d\n", dinic());
    return 0;
}

代码中使用了邻接表存储图的边，使用了bfs和dfs实现了Edmonds-Karp算法。其中bfs用于搜索增广路，dfs用于在增广路上更新流。