USACO Cow Steeplechase：Dinicのアルゴリズム/ポインタの変更が登録されていない

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（）」メソッドのエラーに起因して、無限ループが発生しています。 「後ろ向きエッジ」ポインタを更新しようとすると、意図したとおりに変更が維持されず、結果として同じパスが何度も繰り返されます。

私はポインタを使用するのが非常に新しいので、数時間の検索の後にポインタに関する問題の解決策や説明を見つけることができませんでした。

ご協力いただきありがとうございます。

EDIT：問題を表示するコードの一部に追加されました。

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のインスタンスを宣言していることを最初に観察し、そして：あなたの例で強調

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()方法でありますしたがって、メソッドの終了時に変数がスコープから外れると、そのライフタイムは終了します。これは実際にJavaとは異なり、オブジェクトはヒープ上にのみ割り当てられ、オブジェクトへの参照のみが割り当てられます。

各Edgeでは、もう1つのスタック割り当て済みのEdgeにポインタを設定しますが、そのポインタ値は、指し示された（スタック割り当てされた）オブジェクトの存続期間にのみ有効です。それらを後で参照解除する、すなわちそのメソッドが戻ると、未定義の動作が生成されます。

さらに、vector::push_backcreates a copy of its argumentを理解することは必須です。その意味では、JavaのList.add()とは異なります。これらのコピーには、backwardポインタの値のコピーが含まれており、元のポインターが指しているのと同じスタック割り当てオブジェクトを指しています。これらはベクトルadjacencyのコピーとは異なるオブジェクトなので、隣接ベクトルの要素はお互いを指しません。、ちょうどメソッドが戻る前に、あなたはe

へr

r.backwardsポイント（adjacency[v1]でeのコピー）.backwardsに

• e.backwardsポイントを持っている

  もr

を指します
• （rのコピーはadjacency[v2]）.backwardsはまた、backwardsポインタがそのオブジェクトを指していないため、solve.adjacency[0][0]によって指定されたオブジェクトを変更しないsolve.adjacency[3][0].backwards->flow = 1を行う、あなたの例では、このようe

を指します。 （実際には、一度指し示したオブジェクトの存続期間は終了しているため、割り当てによって未定義の動作が生成されます）solve.adjacency[0][0]に変更がないことは驚くことではありません。

あなたはこれらの問題を解決することができ、いくつかの方法、それらの間

• が指すbackwardポインタを割り当てるあなたのベクトルでそれらに

• をヒープ上Edgeオブジェクトを割り当てる、と店のポインタがあります。正しいベクトル内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(); 
    }