ek算法实现最大流问题

最大流问题的解决方法一般是利用Ford-Fulkerson算法，该算法伪码如下:

for each edge (u, v) ∈ E do
	f[u, v]←0
	f[v, u]←0
end for
while there exists a path P from s to t in the residual network Gf
do
	cf (P)←mine∈P {cf (e)}
	for each edge (u, v) ∈ P do
		f[u, v]←f[u, v] + cf (P)
		f[v, u]← − f[u, v]
	end for
end while

而ek算法是对 Ford-Fulkerson方法的实现，基于BFS。

网上也有许多很好的模板：

最大流问题(EK算法模板)

HDU1532(最大流EK算法模板题)

我自己也写了一个：

/*
 * @Author: YaleXin
 * @Date: 2020-05-30 14:55:40
 * @LastEditTime: 2020-05-30 17:26:38
 * @LastEditors: YaleXin
 * @Description:
 * @FilePath: \my_c_workspace\others\maxFlow.c
 * @祈祷不出现BUG
 */
#include <stdio.h>
#define MAXLEN 10001
#define min(a, b) a < b ? a : b
int capacity[MAXLEN][MAXLEN] = {0};
// 记录路径上的前驱，用于添加反向边
int pre[MAXLEN];
int vertexNum, arcNum;
int BFS(int start, int end) {
    for (int i = 1; i <= vertexNum; i++) pre[i] = -1;
    int flow[vertexNum + 1], queue[vertexNum + 1], front = 0, rear = 0;
    flow[start] = 32767;
    // 源点进队列
    queue[++rear] = start;
    while (front != rear) {
        int frontIndex = queue[++front];
        if (frontIndex == end) break;
        for (int i = 1; i <= vertexNum; i++) {
            // 存在有向边并且点i没有被访问过
            if (i != start && capacity[frontIndex][i] > 0 && pre[i] == -1) {
                pre[i] = frontIndex;
                flow[i] = min(capacity[frontIndex][i], flow[frontIndex]);
                queue[++rear] = i;
            }
        }
    }
    // 残余网络中不存在增广路
    if (pre[end] == -1)
        return -1;
    else
        return flow[end];
}
int getMaxFlow(int S, int T) {
    int minF, preIndex, th, sum = 0;
    while ((minF = BFS(S, T)) != -1) {
        // 更新残留网络
        th = T;
        preIndex = pre[th];
        while (preIndex != -1) {
            capacity[th][preIndex] += minF;
            capacity[preIndex][th] -= minF;
            th = preIndex;
            preIndex = pre[th];
        }
        sum += minF;
    }
    return sum;
}
int main() {
    int SVertex, TVertex;
    // printf("请输入点的个数和有向边的个数以及源点汇点编号：\n");
    scanf("%d%d%d%d", &vertexNum, &arcNum, &SVertex, &TVertex);
    // printf("请依次输入每条有向边的容量，格式为 1 2 3：\n");
    int u, v, c;
    for (int i = 1; i <= arcNum; i++) {
        scanf("%d%d%d", &u, &v, &c);
        // 有可能输入重复边
        capacity[u][v] += c;
    }
    printf("%d", getMaxFlow(SVertex, TVertex));
    return 0;
}
/*

4 6 1 4
1 3 5
1 4 20
1 2 10
3 4 50
3 2 30
2 4 40

*/