對SPOJ FASTFLOW的錯誤回答？

Question

任何人都可以幫我解決這個問題problem我試了幾天。每次我都會遇到錯誤的答案。我用埃德蒙茲 - 卡普法......這是我的代碼：

#include<cstdio> 
    #include<iostream> 
    #include<queue> 
    #include<algorithm> 
    #include<cstring> 
    #define MAXX 900000000 
    using namespace std; 
    long int capacity[5005][5005] ; 
    int graph[5005][5005] , v[5005] , from[5005] ; 
    //Calculating Max Flow using Edmond karp 
    int Max_Flow(int s , int t) 
    { queue<int>Q ; 
     // Bfs to get the paths from source to sink 
     Q.push(s) ; 
     v[s] = 1 ; 
     int r ; 
     long long int min ; 
     while(!Q.empty()) 
     { int p = Q.front() ; 
      Q.pop(); 
      r = 0 ; 
      for(int j = 0 ; graph[p][j]!=0 ; j++) 
      { 
      if(!v[graph[p][j]]&&capacity[p][graph[p][j]]) 
      { Q.push(graph[p][j]) ; from[graph[p][j]] = p ; 
       v[graph[p][j]] = 1 ; 
       if(graph[p][j]==t) 
       { r = 1 ; break ; } 
      } 

      } 
      if(r==1) 
      break ; 
     } 
     r = t ; 
     min = MAXX ; 
     // Caculating the minimum capacity over the path found by BFS   
     while(from[r]!=0) 
     { 
     if(min>capacity[from[r]][r]) 
     min = capacity[from[r]][r] ; 
     r = from[r] ; 
     } 
     r = t ; 
     //Subtracting the min capacity found over the path 
     while(from[r]!=0) 
     { 
     capacity[from[r]][r]-=min; 
     capacity[r][from[r]]+=min; 
     r = from[r] ; 
     } 
     if(min==MAXX) 
     return 0; 
     else 
     return min; 
    } 
    int main() 
    { 
     int t , n , s , c , i , j , k , a , b , p = 0 ; 
     unsigned long long int flow , r ; 
      memset(capacity,0,sizeof(capacity)); 
      memset(from,0,sizeof(from)); 
      memset(graph,0,sizeof(graph)); 
      memset(v,0,sizeof(v)); 
      scanf("%d%d",&n,&c); 
      for(i = 0 ; i<c ; i++) 
      { 
       scanf("%d%d%d",&a,&b,&k); 
       if(b!=a) 
       { 
       capacity[a][b]+=k ; 
       capacity[b][a]+=k ; 
       j = 0 ; 
       r = 0 ; 
       while(graph[a][j]!=0) 
       { if(graph[a][j]==b) 
        { r = 1 ; break ; } 
        j++; 
       } 
       if(!r) graph[a][j] = b ; 

       j = 0 ; 
       r = 0 ; 
       while(graph[b][j]!=0) 
       { if(graph[b][j]==a) 
        { r = 1 ; break ; } 
        j++; 
       } 
       if(!r) graph[b][j] = a ; 
       } 

      } 
      flow = 0 ;  
      r = 1 ; 
      while(r) 
      { flow+=r ; 
      r = Max_Flow(1,n) ; 
      memset(from,0,sizeof(from)); 
      memset(v,0,sizeof(v)); 
      } 
      printf("%lld\n",flow-1); 


      return 0; 
    } 

隨着問題的聲明說：「要注意的是，有可能存在存在重複的邊緣，以及從一個節點到其自身的優勢「。所以我忽略了自循環，並在與這些節點對應的「容量」數組中添加了重複邊的容量。我創建了一個'圖表'，並執行BFS從源到匯來獲取路徑，直到所有路徑都得到增強。我總結出所有最小值，並打印答案......任何人都可以解釋爲什麼錯誤的答案？

Answer 1

假設您有一個簡單的圖表，其中包含10億容量的開始和結束之間的一條邊。

由於您的MAXX < 10億，當您運行Max_Flow時，您會發現一個MAXX流，並錯誤地推斷這意味着沒有找到擴充路徑。

如果是這種情況，那麼只需嘗試用

#define MAXX 1100000000 

和程序可以通過更換

#define MAXX 900000000 

...