简单易懂的Dinic算法C++实现 含算法解释

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

//邻接矩阵存储图 储存容量和流量 
struct Vertex
{
    int c;
    int f;
}G[100][100];

int Edge, Vex; // 边数 节点数 
int layer[100]; //层数数组 
int v_s, v_e, v_c; // 每条边起点、终点和流量 
const int INF = 0x7fffffff;

bool BFS(); // 广度优先BFS构造层次网络 
int DFS(int u, int cp); // 深度优先DFS找寻增广路
int Dinic(); // Dinic算法 

int Dinic() {
    int sum=0, tf=0;
    while (BFS()) {
        while (tf = DFS(1, INF))
            sum += tf;
    }
    return sum;
}

bool BFS()     
{
    queue<int> q;
    memset(layer, 0, sizeof(layer));
    q.push(1);
    layer[1] = 1;
    int u, v;
    while (!q.empty()) {
        u = q.front();
        q.pop();
        for (v = 1; v <= Vex; v++) {
            if (!layer[v] && G[u][v].c>G[u][v].f) {
                layer[v] = layer[u] + 1;
                q.push(v);
            }
        }
    }
    return layer[Vex] != 0;              
}

int DFS(int u, int cp) {         
    int tmp = cp;
    int v, t;
    if (u == Vex)
        return cp;
    for (v = 1; v <= Vex&&tmp; v++) {
        if (layer[u] + 1 == layer[v]) {
            if (G[u][v].c>G[u][v].f) {
                t = DFS(v, min(tmp, G[u][v].c - G[u][v].f));
                G[u][v].f += t;
                G[v][u].f -= t;
                tmp -= t;
            }
        }
    }
    return cp - tmp;
}


int main() {
	printf("请输入边数和节点数(空格隔开)：\n"); 
    while (scanf("%d%d", &Edge, &Vex)) {
        memset(G, 0, sizeof(G));
        if(Edge!=0) printf("请输入每条边起点 终点 权值：\n") ;
        while (Edge--) {
            scanf("%d%d%d", &v_s, &v_e, &v_c);
            G[v_s][v_e].c += v_c;
        }
        int max_c = Dinic();
        printf("\n汇点最大流量为：%d", max_c);
    }
    return 0;
}