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

Question

Disclaimer: Not all of the code I used to attempt to solve the problem is needed to answer my question, but I will provide the rest if it is needed.

Problem (If Context is Needed): 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;
    }
};

The problem essentially narrows down to finding the minimum number of vertices that make up the vertex cover of a bipartite graph. I was able to successfully construct said graph in the unseen part of my code, but my problem lies in running Dinic's algorithm on it.

I keep getting an infinite loop when I do so, which stems from an error in the "dfs()" method. Whenever I try to update a "backwards Edge" pointer, it does not maintain the change as intended, resulting in the same path being taken over and over again.

I am very new to using pointers, and I have not been able to find a solution or explanation for my pointer-related problem after hours of searching.

Please help, and thanks in advance!

EDIT: Added in a segment of code that displays the problem.

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

The main problems highlighted by your example are in the add() method:

    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);
    }

Observe first that you are declaring the Edge instances designated by e and r on the stack, and therefore that their lifetime ends when the variables go out of scope at the end of the method. This is indeed different from Java, in which objects can be allocated only on the heap, and you have only references to them.

In each Edge you set a pointer to the other stack-allocated Edge, but that pointer value is only useful for the lifetime of the pointed-to (stack-allocated) objects; dereferencing them later, i.e. after that method returns, produces undefined behavior.

Moreover, it is essential to understand that vector::push_back creates a copy of its argument; in that sense it is unlike, say, Java's List.add(). Those copies contain copies of the values of the backward pointers, pointing to the same stack-allocated objects that the originals' pointers point to. Since these are different objects from the copies in the adjacency vectors, the elements of the adjacency vectors do not point to each other.

That is, just before the method returns, you have

• e.backwards points to r
• r.backwards points to e
• (a copy of e in adjacency[v1]).backwards also points to r
• (a copy of r in adjacency[v2]).backwards also points to e

Thus, in your example, performing solve.adjacency[3][0].backwards->flow = 1 does not modify the object designated by solve.adjacency[0][0], because the backwards pointer does not point to that object. (In fact, the lifetime of the object to which it once pointed is over, so that assignment produces undefined behavior.) It is not surprising, then, that you do not observe any change in solve.adjacency[0][0].

There are several ways you could fix these problems, among them

• allocate the Edge objects on the heap, and store pointers to them in your vector

• assign backward pointers that point to the correct in-vector Edges

The latter can be implemented in add(), without modifying anything else; this should do it:

    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(); 
    }