c - 深度优先搜索的 Ford-Fulkerson 算法

Question

我正在做实现 Ford-Fulkerson 算法的作业，他们说我们应该使用 DFS 进行路径查找，但我被困在某个地方。我没有发布代码，因为它的本地化太多了。实际上我的 DFS 算法运行良好，但死胡同会导致问题，例如，如果我运行我的代码，我会得到这样的 DFS 输出

0=>1 1=>2 1=>3 3=>5

它从 0 开始，以 5 结束，但 1=>2 部分对我的算法来说是不必要的，我也使用 [N][2] 矩阵存储我的路径。我的问题是如何消除结果矩阵中的死胡同（也许在 DFS 递归内部？）

Answer 1

您应该执行 DFS 以找到源和接收器之间的一些路径。然后，当 dfs 重新调整时，您应该添加一个流

这是一个例子。函数“发送”是一个 DFS。请注意，我将搜索期间找到的最小容量值与 DFS 一起传递：

https://github.com/juanplopes/icpc/blob/master/uva/820.cpp

int send(int s, int t, int minn) {
    V[s] = true;

    if (s==t) return minn;

    for(int i=1; i<=n; i++) {
        int capacity = G[s][i]-F[s][i];
        if (!V[i] && capacity > 0) {
            if (int sent = send(i, t, min(minn, capacity))) {
                F[s][i] += sent;
                F[i][s] -= sent;
                return sent;
            }
        }
    }

    return 0;
}