2013-10-18 154 views
1

我在topcoder站點學習push-relabel算法:http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxflowPushRelabel 我認爲實現有問題。飽和時,節點如何將多餘的流量推回節點。例如:push-relabel算法的實現

enter image description here

雖然找到最大流量從1到3,在一個階段我需要從2推回流1(因爲2不具有外向邊緣)。但是在先進先出算法的代碼實現中,行號的循環從0 to G[u].size()運行。由於2從2到1沒有任何邊緣,它如何將流量推回到1?

這是我蹩腳的實現如果需要的話:

#define DEBUG  //comment when you have to disable all debug macros. 
#define LOCAL 
#define NDEBUG //comment when all assert statements have to be disabled. 
#include <iostream> 
#include <cstring> 
#include <sstream> 
#include <cstdlib> 
#include <cstdio> 
#include <cmath> 
#include <vector> 
#include <set> 
#include <map> 
#include <bitset> 
#include <climits> 
#include <ctime> 
#include <algorithm> 
#include <functional> 
#include <stack> 
#include <queue> 
#include <list> 
#include <deque> 
#include <sys/time.h> 
#include <iomanip> 
#include <cstdarg> 
#include <utility> //std::pair 
#include <cassert> 
#define tr(c,i) for(typeof(c.begin()) i = (c).begin(); i != (c).end(); i++) 
#define present(c,x) ((c).find(x) != (c).end()) 
#define all(x) x.begin(), x.end() 
#define pb push_back 
#define mp make_pair 
#define log2(x) (log(x)/log(2)) 
#define ARRAY_SIZE(arr) (1[&arr]-arr)  
#define INDEX(arr,elem)  (lower_bound(all(arr),elem)-arr.begin()) 
#define lld long long int 
#define MOD 1000000007 
#define gcd __gcd 
#define equals(a,b) (a.compare(b)==0) //for strings only 
using namespace std; 



struct Graph{ 
    lld numV; 
    vector<lld> *adj; 
    lld **flow, **cap, **cf, *height, *excess; 
     inline void SET0(lld *array) 
     { 
     for(lld i=0;i<=numV;i++) 
      array[i]=0; 
     } 
    Graph(lld _numV) 
     { 
     numV=_numV; 
     lld i; 
     /* allocating memory....*/ 
     flow = new lld*[numV+1]; 
     for(i=0;i<=numV;i++) 
      flow[i] = new lld[numV+1], SET0(flow[i]); 
     cap = new lld*[numV+1]; 
     for(i=0;i<=numV;i++) 
      cap[i] = new lld[numV+1], SET0(cap[i]); 
     cf = new lld*[numV+1]; 
     for(i=0;i<=numV;i++) 
      cf[i] = new lld[numV+1], SET0(cf[i]); 

     height = new lld[numV+1]; 
     excess = new lld[numV+1]; 
     SET0(height); 
     SET0(excess); 
     adj = new vector<lld>[numV+1]; 
     } 
    void addEdge(lld u, lld v, lld uv) 
     { 
     adj[u].push_back(v); 
     cap[u][v] = uv; 
     cf[u][v] = uv; 
     } 

    void initialize_preflow(lld source) 
     { 
     lld i, v; 
     height[source] = numV-1; 

     tr(adj[source],it) 
     { 
      v = *it; 
      flow[source][v] = cap[source][v]; 
      flow[v][source] = -cap[source][v]; 
      excess[v] += cap[source][v]; 
      excess[source] -=cap[source][v]; 
      cf[source][v] = cap[source][v]-flow[source][v]; 
      cf[v][source] = cap[v][source]-flow[v][source]; 
     } 
     } 
    void push(lld u, lld v) 
     { 
     lld push_val = min(cf[u][v], excess[u]); 
     flow[u][v] += push_val; 
     flow[v][u] = -flow[u][v]; 
     excess[u] -=push_val; 
     excess[v] +=push_val; 
     cf[u][v] = cap[u][v]-flow[u][v]; 
     cf[v][u] = cap[v][u]-flow[v][u]; 
     } 
    lld max_flow(lld source, lld sink) 
     { 
     initialize_preflow(source); 
     queue<lld> q; 
     bool considered[numV+1]; 
     lld u, v, m, i; 
     memset(considered, false, sizeof(considered)); 
     tr(adj[source], it) 
     { 
      v = *it; 
      if(v!=sink) 
      { 
       q.push(v); 
       considered[v] = true; 
      } 
     } 
     bool flag; 
     u = -1; 
     while(!q.empty()) 
     { 

      u = q.front(); 
      m = -1; 
      for(i=0;i<adj[u].size() && excess[u]>0; i++) 
      { 

       v = adj[u][i]; 
       if(cf[u][v]>0) 
       { 
        if(height[u]>height[v]) 
        { 
        push(u,v); 
        if(!considered[v] && v!=sink && v!=source) 
        { 
         considered[v] = true; 
         q.push(v); 
        } 
        } 
        else if(m==-1) m = height[v]; 
        else m = min(m, height[v]); 
       } 
      } 

      if(adj[u].empty()) {q.pop();continue;} 
      if(excess[u]!=0) height[u] = m+1; 
      else 
      { 
       q.pop(); 
       considered[u] = false; 
      } 
     } 
     return excess[sink]; 
     } 

}; 

template<class T> 
inline void inputInt(T &n) 
{ 
    n=0; 
    T ch=getchar_unlocked(); 
    while(ch < '0' || ch > '9') 
     ch=getchar_unlocked(); 
     while( ch >= '0' && ch <= '9') 
     n = (n<<3)+(n<<1) + ch-'0', ch=getchar_unlocked(); 
} 

int main() 
{ 
#ifdef LOCAL 
    freopen("input.in","r",stdin); 
#endif 
    lld e,u,v,n,c; 
    //cout<<"V:"<<endl; 
    cin>>n>>e; 

    Graph g(n); 
    while(e--) 
    { 

     inputInt(u); 
     inputInt(v); 
     inputInt(c); 
     if(u!=v) 
     { 
     if(g.cf[u][v]) 
      g.cf[u][v]=g.cf[v][u]=g.cap[u][v]=g.cap[v][u]+c; 
     else g.addEdge(u,v,c); 
     } 
    } 
    cout<<g.max_flow(1,n)<<endl; 

} 
+4

聖牆'#包括'蝙蝠俠! –

+3

讓你'#定義'太多。 –

+1

對不起,我通常有一個預處理器的默認列表。 – sudeepdino008

回答

1

我只是重新實現推重標記算法從TopCoder公司。我完全面臨同樣的問題。這是一種糟糕的描述,在這個問題上。但是,解決方案是,您可以在有向圖的相反方向上爲圖添加一條邊 - 每條邊的容量爲0!

E.g.在上面的示例圖中添加邊(3,1)和邊(2,1),兩者的容量均爲0.

如果你有一個無向圖,當然這個問題是不必要的,因爲你添加了兩個相同的邊u,v)和(v,u)與您的圖形具有相同的容量。

我希望我可以幫忙,如果沒有,只要問:)