maxflow算法返回結果爲零

-1

以下代碼返回零作爲輸出，請告訴我什麼是錯誤的？maxflow算法返回結果爲零

#include<iostream> 
#define MAX 100 
using namespace std; 
int graph[MAX][MAX]; 
int queue[MAX]; 
int head,tail; 
int parent[MAX]; 
int V,E; 
int s,t,fTotal; 
int F[MAX][MAX]; 

//breadth First search 
bool reachable(int s,int t){ 
    bool found=false; 
    head=tail=0; 
    int vq; 
    memset(parent,255,sizeof(parent)); 
    queue[tail++]=s; 
    parent[s]=s; 
    while(head< tail && ! found){ 
     vq=queue[head++]; 
     for(int i=0;i<V;i++){ 
      //Parents also made the function as visit vector 
      if(graph[vq][i] && parent[i]==-1) 
       queue[tail++]=i; 
      parent[i]=vq; 
      if(i==t){ 
       found=true; 
       break; 
      } 
     } 
    } 
    return found; 
} 

void maxflow(){ 
    int vj,min; 
    fTotal=0; 
    while(reachable(s,t)){ 
     //Gets the minimum possible capacity in edges of the path s to t 
     min=graph[parent[t]][t]; 
     vj=t; 
     while(parent[vj]!=vj){ 
      if(graph[parent[vj]][vj]<min) 
       min=graph[parent[vj]][vj]; 
      vj=parent[vj]; 
     } 

     vj=t; 
     while(parent[vj]!=vj){ 

      graph[parent[vj]][vj]-=min; 
      graph[vj][parent[vj]]+=min; 
      F[parent[vj]][vj]+=min; 
      vj=parent[vj]; 
     } 
     fTotal+=min; 
    } 
} 

bool read(){ 
    cin>>V>>E>>s>>t; 
    if(!V && !E) return false; 
    memset(graph,0,sizeof(graph)); 
    memset(queue,0,sizeof(queue)); 
    memset(F,0,sizeof(F)); 
    int v1,v2,val; 
    for(int i=0;i<E;i++){ 
     cin>>v1>>v2>>val; 
     graph[v1][v2]=val; 
    } 
    return true; 
} 

int main(){ 
    while(read()){ 
     maxflow(); 
     cout<<" max flow from s to t is : "<<fTotal<<endl; 
    } 
    return 0; 
}

當輸入被以下，我已進入節點6和8的邊緣，源1和接收器頂點6.

(1,2)  2 
    (1,3)  3 
    (2,4)  3 
    (3,4)  1 
    (2,5)  1 
    (3,5)  1 
    (4,6)  2 
    (5,6)  3

來源

2011-11-04 dato datuashvili

如果這純粹是一個編程問題，它屬於堆棧溢出。我不清楚這與統計數據有什麼關係。請參閱[常見問題]（http://stats.stackexchange.com/faq），瞭解本網站最適合的問題。 –

有什麼幫助嗎？我已經展示了一切 –

你reachable()函數不是一個廣度優先搜索。例如，查看this pseudo-code並將其與您的比較。你做得很好，直到「爲每個邊緣」部分，而不是「爲每個節點」做一個「它只是從那裏分開」。

您還在混合使用基於0和基於1的索引：輸入爲基於1的索引，但在reachable()中，迴路for(int i=0;i<V;i++)基於0。選擇一個系統並保持一致。

該代碼還有很多其他潛在的問題，一旦您修復了reachable()，會導致更多的問題。我會建議CodeReview網站獲得進一步的反饋意見。

來源

2011-11-04 13:23:28 uesp

maxflow算法返回結果爲零

回答

相關問題