写dinic网络流 C++

这里是一份Dinic算法的C语言实现代码，供您参考：

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

#define MAX_N 10010
#define MAX_M 100010
#define INF INT_MAX

typedef struct {
    int v, w, nxt;
} edge_t;

edge_t edges[MAX_M << 1];
int head[MAX_N], cur[MAX_N], dep[MAX_N], que[MAX_N];
int n, m, s, t, cnt = 1;

void add_edge(int u, int v, int w) {
    edges[++cnt] = (edge_t){v, w, head[u]};
    head[u] = cnt;
    edges[++cnt] = (edge_t){u, 0, head[v]};
    head[v] = cnt;
}

bool bfs() {
    int h = 0, t = 0;
    memset(dep, 0, sizeof(dep));
    dep[s] = 1;
    que[t++] = s;
    while (h < t) {
        int u = que[h++];
        for (int i = head[u]; i; i = edges[i].nxt) {
            int v = edges[i].v, w = edges[i].w;
            if (w && !dep[v]) {
                dep[v] = dep[u] + 1;
                que[t++] = v;
            }
        }
    }
    return dep[t] != 0;
}

int dfs(int u, int minf) {
    if (u == t || !minf) return minf;
    int flow = 0;
    for (int &i = cur[u]; i; i = edges[i].nxt) {
        int v = edges[i].v, w = edges[i].w;
        if (dep[v] == dep[u] + 1 && w) {
            int f = dfs(v, w < minf ? w : minf);
            edges[i].w -= f;
            edges[i ^ 1].w += f;
            flow += f;
            minf -= f;
            if (!minf) break;
        }
    }
    if (!flow) dep[u] = -1;
    return flow;
}

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

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u, v, w);
    }
    printf("%d\n", dinic());
    return 0;
}

其中，`s`和`t`分别表示源点和汇点，`n`和`m`分别表示点数和边数。`add_edge`函数用于添加一条边，`bfs`函数用于进行BFS遍历，`dfs`函数用于进行DFS遍历，`dinic`函数则是Dinic算法的核心函数。最后，我们只需要输入点数、边数、源点和汇点，然后输入每条边的起点、终点和容量，就可以输出最大流了。