topcoder push-relabel implementation

Discussion on all problems hosted at SPOJ

topcoder push-relabel implementation

Postby sudeep » Fri Oct 18, 2013 23:25

I was learning the push-relabel algorithm from the topcoder site:, I think there is something wrong with the implementation. How can a node push back the excess flow to the node when it is saturated. For instance:

Code: Select all
1->2 [weight=4]
1->3 [weight=5]

While finding the max flow from 1 to 3, at one stage I'll need to push back the flow from 2 to 1(since 2 has no outgoing edges). But in the code implementation of the First-in First-out algorithm, the loop at line number 16 runs from
Code: Select all
0 to G[u].size()
. Since 2 doesn't have any edge from 2 to 1, how can it push back the flow?

Here is my implementation of required:

Code: Select all
#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) (    //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++)
   Graph(lld _numV)
         lld i;
         /* allocating memory....*/
         flow = new lld*[numV+1];
            flow[i] = new lld[numV+1], SET0(flow[i]);
         cap = new lld*[numV+1];
            cap[i] = new lld[numV+1], SET0(cap[i]);
         cf = new lld*[numV+1];
            cf[i] = new lld[numV+1], SET0(cf[i]);
         height = new lld[numV+1];
         excess = new lld[numV+1];
         adj = new vector<lld>[numV+1];
   void addEdge(lld u, lld v, lld uv)
         cap[u][v] = uv;
         cf[u][v] = uv;

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

            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)
         queue<lld> q;
         bool considered[numV+1];
         lld u, v, m, i;
         memset(considered, false, sizeof(considered));
         tr(adj[source], it)
            v = *it;
               considered[v] = true;
         bool flag;
         u = -1;
            u = q.front();
            m = -1;
            for(i=0;i<adj[u].size() && excess[u]>0; i++)

               v = adj[u][i];
                     if(!considered[v] && v!=sink && v!=source)
                        considered[v] = true;
                  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;
               considered[u] = false;
         return excess[sink];


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

int main()
#ifdef LOCAL
   lld e,u,v,n,c;

   Graph g(n);
         else g.addEdge(u,v,c);

Posts: 8
Joined: Fri Sep 27, 2013 10:51

Return to ProblemSet Archive

Who is online

Users browsing this forum: No registered users and 1 guest