c++ - USACO 牛栏板 : Dinic's Algorithm/Changes to Pointer Not Registering

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()”方法中的错误造成的。每当我尝试更新“向后边缘”指针时，它都不会按预期保持更改，导致一遍又一遍地采用相同的路径。

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

请帮忙，提前致谢!

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

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 不同，在 Java 中，对象只能在堆上分配，并且您只有对它们的引用。

在每个 Edge 中，您都设置了一个指向其他堆栈分配的 Edge 的指针，但该指针值仅在指向的(堆栈-分配)对象；稍后取消引用它们，即在该方法返回之后，会产生未定义的行为。

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

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

• 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]。

有几种方法可以解决这些问题，其中包括

• 在堆上分配 Edge 对象，并将指向它们的指针存储在您的 vector 中

• 分配指向正确的 vector 内边

  的向后指针

后者可以在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(); 
    }