このMCMFコードに何が問題なのか分かりません

Question

私はMCMF（Minimum Cost - Maximum Flow）アルゴリズムを研究しています。

MCMFコードのコード化が終了しましたが、ランタイムエラーが発生し続けます。

私は理由を見つけることができません。

私は、それが起こる理由を見つけようとしましたが、解決策を見つけることができませんでした。

入力データに問題はないと思います。

ここに私のコードです。

struct MCMF{ 
    struct edge{ 
     int to, cap, cost, rev; 
    }; 
    int size, src, sink; 
    vector<vector<edge> > G; 
    vector<int> dist, par, edgeIdx; 
    MCMF(int size, int src, int sink){ 
     G = vector<vector<edge> >(size); 
     par = vector<int>(size); 
     edgeIdx = vector<int>(size); 
     this->size = size; 
     this->src = src; 
     this->sink = sink; 
    } 
    bool spfa(){ 
     dist = vector<int>(size, inf); 
     vector<bool> inQ = vector<bool>(size, false); 
     queue<int> q; 
     q.push(src); 
     inQ[src] = true; 
     dist[src] = 0; 
     while(!q.empty()){ 
      int here = q.front(); 
      q.pop(); 
      inQ[here] = false; 
      for(int i = 0 ; i < (int)G[here].size(); i++){ 
       auto e = G[here][i]; 
       if(e.cap > 0 && dist[here] + e.cost < dist[e.to]) { 
        dist[e.to] = dist[here] + e.cost; 
        par[e.to] = here; 
        edgeIdx[e.to] = i; 
        if(!inQ[e.to]) q.push(e.to), inQ[e.to] = true; 
       } 
      } 
     } 
     return dist[sink] != inf; 
    } 
    pair<int,int> getMCMF(){ 
     int maxFlow = 0; 
     int minCost = 0; 
     while(1){ 
      if(!spfa()) break; 
      int minFlow = inf; 
      int costSum = 0; 
      for(int p = sink; p != par[p]; p = par[p]){ 
       auto& e = G[par[p]][edgeIdx[p]]; 
       minFlow = min(minFlow, e.cap); 
       costSum += e.cost; 
      } 
      for(int p = sink; p != par[p]; p = par[p]){ 
       auto& e = G[par[p]][edgeIdx[p]]; 
       e.cap -= minFlow; 
       G[e.to][e.rev].cap += minFlow; 
      } 
      maxFlow += minFlow; 
      minCost += costSum * minFlow; 
     } 
     return {maxFlow, minCost}; 
    } 
    void addEdge(int from, int to, int cap, int cost){ 
     G[from].push_back({to, cap, cost, (int)G[to].size()}); 
     G[to].push_back({from, 0, -cost, (int)G[from].size()-1}); 
    } 
}; 

Answer 1

は、私はあなたが

for(int p = sink; p != par[p]; p = par[p]) 

を変更したくない場合は、コード

par[src] = src 

を追加すべきだと思うし、私はそれはあなたが変更した場合、より良いことだと思う

p != par[p] 

〜

p != src 

forループ。

それはコードを理解するために、より明確なので、あなたは私が言った部分を修正する場合は、「パーが[ソース] = SRC」ここ

がフルコードで追加する必要はありません

struct MCMF{ 
    struct edge{ 
     int to, cap, cost, rev; 
    }; 
    int size, src, sink; 
    vector<vector<edge> > G; 
    vector<int> dist, par, edgeIdx; 
    MCMF(int size, int src, int sink){ 
     G = vector<vector<edge> >(size); 
     par = vector<int>(size); 
     edgeIdx = vector<int>(size); 
     this->size = size; 
     this->src = src; 
     this->sink = sink; 
    } 
    bool spfa(){ 
     dist = vector<int>(size, inf); 
     vector<bool> inQ = vector<bool>(size, false); 
     queue<int> q; 
     q.push(src); 
     inQ[src] = true; 
     dist[src] = 0; 
     while(!q.empty()){ 
      int here = q.front(); 
      q.pop(); 
      inQ[here] = false; 
      for(int i = 0 ; i < (int)G[here].size(); i++){ 
       auto e = G[here][i]; 
       if(e.cap > 0 && dist[here] + e.cost < dist[e.to]) { 
        dist[e.to] = dist[here] + e.cost; 
        par[e.to] = here; 
        edgeIdx[e.to] = i; 
        if(!inQ[e.to]) q.push(e.to), inQ[e.to] = true; 
       } 
      } 
     } 
     return dist[sink] != inf; 
    } 
    pair<int,int> getMCMF(){ 
     int maxFlow = 0; 
     int minCost = 0; 
     while(1){ 
      if(!spfa()) break; 
      int minFlow = inf; 
      int costSum = 0; 
      for(int p = sink; p != src; p = par[p]){ 
       auto& e = G[par[p]][edgeIdx[p]]; 
       minFlow = min(minFlow, e.cap); 
       costSum += e.cost; 
      } 
      for(int p = sink; p != src; p = par[p]){ 
       auto& e = G[par[p]][edgeIdx[p]]; 
       e.cap -= minFlow; 
       G[e.to][e.rev].cap += minFlow; 
      } 
      maxFlow += minFlow; 
      minCost += costSum * minFlow; 
     } 
     return {maxFlow, minCost}; 
    } 
    void addEdge(int from, int to, int cap, int cost){ 
     G[from].push_back({to, cap, cost, (int)G[to].size()}); 
     G[to].push_back({from, 0, -cost, (int)G[from].size()-1}); 
    } 
};