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

Question

我正在做实现福特-富尔克森算法的家庭作业，他们说我们应该使用DFS来寻找路径，但我被困在了某个地方。我没有发布代码，因为它的本地化程度太高了。实际上，我的DFS算法工作得很好，但是死胡同导致了一个问题，例如，如果我运行我的代码，我得到的DFS输出是这样的

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

它从0开始，以5结束，但1=>2部分对于我的算法来说是不安全的，我还使用N矩阵存储我的路径。我的问题是，如何删除结果矩阵中的死胡同(也许在DFS递归中？)

Answer 1

您应该执行DFS来查找源和宿之间的某个路径。然后，当dfs重新优化时，您应该添加一个流

下面是一个例子。函数"send“是一个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;
}