USACO 奶牛障碍赛：Dinic 的 Algorithm/Changes 指向未注册的指针

Question

免责声明：并非所有我用来尝试解决问题的代码都需要回答我的问题，但如果需要，我会提供其余部分。

问题（如果需要上下文）：http://www.usaco.org/index.php?page=viewproblem2&cpid=93

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>

using namespace std;

#define INF 1000000000

struct Edge{
    int from, to, cap, flow;
    Edge* backwards;
    Edge(int a, int b, int c, int d): from(a), to(b), cap(c), flow(d) {}
};

struct Dinic{
    int n, source, sink, dist [1000];
    queue<int> q;
    vector<Edge> adjacency [1000];
    bool blocked [1000];
    Dinic(int x): n(x), source(n++), sink(n++) { }
    void add(int v1, int v2, int c, int f){
        Edge e(v1, v2, c, f); Edge r(v2, v1, 0, 0);
        e.backwards = &r; r.backwards = &e;
        adjacency[v1].push_back(e); adjacency[v2].push_back(r);
    }
    bool bfs(){
        q = queue<int>(); fill_n(dist, 1000, -1); dist[sink] = 0; q.push(sink);
        while(q.size() > 0){
            int node = q.front(); q.pop();
            if(node == source) return true;
            for(int i = 0; i < adjacency[node].size(); i++){
                if(adjacency[node][i].backwards->cap > adjacency[node][i].backwards->flow && dist[adjacency[node][i].to] == -1){
                    dist[adjacency[node][i].to] = dist[node]+1;
                    q.push(adjacency[node][i].to);
                }
            }
        }
        return dist[source] != -1;
    }
    int dfs(int pos, int mini){
        if(pos == sink) return mini;
        int flowy = 0;
        for(int i = 0; i < adjacency[pos].size(); i++){
            int curr = 0;
            if(!blocked[adjacency[pos][i].to] && dist[adjacency[pos][i].to] == dist[pos]-1 && adjacency[pos][i].cap > adjacency[pos][i].flow){
                curr = dfs(adjacency[pos][i].to, min(mini-flowy, adjacency[pos][i].cap-adjacency[pos][i].flow));
                adjacency[pos][i].flow += curr; adjacency[pos][i].backwards->flow -= adjacency[pos][i].flow;
                flowy += curr;
            }
            if(flowy == mini) return flowy;
        }
        blocked[pos] = flowy != mini;
        return flowy;
    }
    int flow(){
        int ret = 0; fill_n(blocked, 1000, false);
        while(bfs()){
            fill_n(blocked, 1000, false);
            ret += dfs(source, INF);
            cout << ret << endl;
        }
        return ret;
    }
};

问题本质上缩小为找到构成二分图顶点覆盖的最小顶点数。我能够在我的代码的看不见的部分成功地构建所述图，但我的问题在于运行 Dinic 的算法。

当我这样做时，我一直遇到无限循环，这是由于 "dfs()" 方法中的一个错误。每当我尝试更新 "backwards Edge" 指针时，它不会按预期保持更改，导致一遍又一遍地采用相同的路径。

我对使用指针还很陌生，经过数小时的搜索，我仍无法找到与指针相关的问题的解决方案或解释。

请帮忙，提前致谢！

编辑：添加了一段显示问题的代码。

Dinic solve(3);
solve.add(0, 3, 1, 0);
solve.adjacency[3][0].backwards->flow = 1;
cout << solve.adjacency[0][0].flow << endl; //prints out 0 instead of 1

Answer 1

您的示例突出显示的主要问题在 add() 方法中：

    void add(int v1, int v2, int c, int f){
        Edge e(v1, v2, c, f); Edge r(v2, v1, 0, 0);
        e.backwards = &r; r.backwards = &e;
        adjacency[v1].push_back(e); adjacency[v2].push_back(r);
    }

首先请注意，您在堆栈上声明由 e 和 r 指定的 Edge 个实例，因此当变量超出范围时它们的生命周期结束方法结束。这确实不同于Java，其中对象只能在堆上分配，并且您只有对它们的引用。

在每个 Edge 中，您都设置了一个指向另一个堆栈分配 Edge 的指针，但该指针值仅在指向（堆栈分配）对象的生命周期内有用；稍后取消引用它们，即在该方法 returns 之后，会产生未定义的行为。

此外，必须了解vector::push_back creates a copy of its argument；从这个意义上说，它不同于 Java 的 List.add()。这些副本包含 backward 指针值的副本，指向与原始指针指向相同的堆栈分配对象。由于这些对象与 adjacency 向量中的副本不同，因此邻接向量的元素不指向彼此。

也就是说，就在方法 returns 之前，您有

e.backwards指向r
r.backwards指向e
（adjacency[v1]中e的副本）.backwards也指向r
（adjacency[v2]中r的副本）.backwards也指向e

因此，在您的示例中，执行 solve.adjacency[3][0].backwards->flow = 1 不会修改 solve.adjacency[0][0] 指定的对象，因为 backwards 指针不指向该对象。（事实上，它曾经指向的对象的生命周期已经结束，因此赋值会产生未定义的行为。）因此，您没有观察到 solve.adjacency[0][0].[=44= 中的任何变化也就不足为奇了。 ]

您可以通过多种方式解决这些问题，其中包括

在堆上分配 Edge 个对象，并将指向它们的指针存储在您的向量中
分配 backward 指向正确 in-vector 的指针 Edges

后者可以在add()中实现，无需修改任何其他内容；应该这样做：

    void add(int v1, int v2, int c, int f){
        Edge e(v1, v2, c, f);
        Edge r(v2, v1, 0, 0);

        adjacency[v1].push_back(e);
        adjacency[v2].push_back(r);
        adjacency[v1].back().backwards = &adjacency[v2].back();
        adjacency[v2].back().backwards = &adjacency[v1].back(); 
    }

USACO 奶牛障碍赛：Dinic 的 Algorithm/Changes 指向未注册的指针

USACO Cow Steeplechase: Dinic's Algorithm/Changes to Pointer Not Registering

c++

pointers

max-flow