Facebook
From Smelly Stork, 7 Months ago, written in C++.
Embed
Download Paste or View Raw
Hits: 154
  1. class Flow {
  2. private:
  3.     long long int V, E, S, T;
  4.     long long int *excess;
  5.     long long int *height;
  6.     vector<Edge> *graph;
  7.     queue<long long int> active;
  8.     long long int *positionInAdj;
  9.     long long int counter;
  10.  
  11.  
  12. public:
  13.     Flow(long long int V, long long int E) {
  14.         Flow::V = V;
  15.         Flow::E = E;
  16.         Flow::graph = new vector<Edge>[Flow::V + 1];
  17.         Flow::excess = new long long int[Flow::V + 1];
  18.         Flow::height = new long long int[Flow::V + 1];
  19.         Flow::positionInAdj = new long long int[Flow::V + 1];
  20.         counter = 0;
  21.     }
  22.  
  23.     virtual ~Flow() {
  24.         delete[] Flow::graph;
  25.         delete[] Flow::excess;
  26.         delete[] Flow::height;
  27.         delete[] Flow::positionInAdj;
  28.     }
  29.  
  30.     void addEdge(long long int from, long long int to, long long int cap);
  31.  
  32.     void setSource(long long int S);
  33.  
  34.     void setSink(long long int T);
  35.  
  36.     void clearPositionInAdj();
  37.  
  38.     long long int getFlow();
  39.  
  40.     void bfs(long long int start);
  41.  
  42.     void preFlow();
  43.  
  44.     void relabel(long long int u);
  45.  
  46.     void discharge(long long int u);
  47.  
  48.     void push(long long int u, Edge &edge);
  49.  
  50.     void globalRelabeling();
  51. };