0

我一直在尝试理解这段代码；它是 C++ 中 push-relabel 算法的实现：

// Adjacency list implementation of FIFO push relabel maximum flow
// with the gap relabeling heuristic.  This implementation is
// significantly faster than straight Ford-Fulkerson.  It solves
// random problems with 10000 vertices and 1000000 edges in a few
// seconds, though it is possible to construct test cases that
// achieve the worst-case.
//
// Running time:
//     O(|V|^3)
//
// INPUT: 
//     - graph, constructed using AddEdge()
//     - source
//     - sink
//
// OUTPUT:
//     - maximum flow value
//     - To obtain the actual flow values, look at all edges with
//       capacity > 0 (zero capacity edges are residual edges).

#include <cmath>
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

typedef long long LL;

struct Edge {
  int from, to, cap, flow, index;
  Edge(int from, int to, int cap, int flow, int index) :
    from(from), to(to), cap(cap), flow(flow), index(index) {}
};

struct PushRelabel {
  int N;
  vector<vector<Edge> > G;
  vector<LL> excess;
  vector<int> dist, active, count;
  queue<int> Q;

  PushRelabel(int N) : N(N), G(N), excess(N), dist(N), active(N), count(2*N) {}

  void AddEdge(int from, int to, int cap) {
    G[from].push_back(Edge(from, to, cap, 0, G[to].size()));
    if (from == to) G[from].back().index++;
    G[to].push_back(Edge(to, from, 0, 0, G[from].size() - 1));
  }

  void Enqueue(int v) { 
    if (!active[v] && excess[v] > 0) { active[v] = true; Q.push(v); } 
  }

  void Push(Edge &e) {
    int amt = int(min(excess[e.from], LL(e.cap - e.flow)));
    if (dist[e.from] <= dist[e.to] || amt == 0) return;
    e.flow += amt;
    G[e.to][e.index].flow -= amt;
    excess[e.to] += amt;    
    excess[e.from] -= amt;
    Enqueue(e.to);
  }

  void Gap(int k) {
    for (int v = 0; v < N; v++) {
      if (dist[v] < k) continue;
      count[dist[v]]--;
      dist[v] = max(dist[v], N+1);
      count[dist[v]]++;
      Enqueue(v);
    }
  }

  void Relabel(int v) {
    count[dist[v]]--;
    dist[v] = 2*N;
    for (int i = 0; i < G[v].size(); i++) 
      if (G[v][i].cap - G[v][i].flow > 0)
    dist[v] = min(dist[v], dist[G[v][i].to] + 1);
    count[dist[v]]++;
    Enqueue(v);
  }

  void Discharge(int v) {
    for (int i = 0; excess[v] > 0 && i < G[v].size(); i++) Push(G[v][i]);
    if (excess[v] > 0) {
      if (count[dist[v]] == 1) 
    Gap(dist[v]); 
      else
    Relabel(v);
    }
  }

  LL GetMaxFlow(int s, int t) {
    count[0] = N-1;
    count[N] = 1;
    dist[s] = N;
    active[s] = active[t] = true;
    for (int i = 0; i < G[s].size(); i++) {
      excess[s] += G[s][i].cap;
      Push(G[s][i]);
    }

    while (!Q.empty()) {
      int v = Q.front();
      Q.pop();
      active[v] = false;
      Discharge(v);
    }

    LL totflow = 0;
    for (int i = 0; i < G[s].size(); i++) totflow += G[s][i].flow;
    return totflow;
  }
};

代码可以编译并且可以工作，但我不明白我应该如何将输入传递给它。理想情况下，一个main()函数应该读取源和接收器（无论如何它们都是“虚构的”，并且只是算法工作所必需的），然后是构建图形所需的所有数据AddEdge()。但是如何做到这一点目前超出了我的范围。

我的main()应该是这样的

int main()
{
    int source, sink;
    vector < vector < int > > graph;
    std::cin >> source >> sink;
    //here should be the nested for loops to read in the graph

    // and here the arguments should be passed to AddEdge
    return 0;
}

我认为这source应该用于初始化 some Edge.froms，它应该与sinkand some Edge.tos 类似，但我不知道如何构建图形。

4

1 回答 1

1

创建PushRelabel(N)具有 N 个节点的结构实例：

struct PushRelabel prGraph(N);

然后使用该AddEdge函数构建图形。假设好的边缘结构，这可以做到

std::vector<Edge> edges;

for( auto e : edges )
  prGraph.AddEdge(e.from, e.to, e.cap);

然后有一个GetMaxFlow函数获取你的源s和接收器t，它计算并返回流：

int s, t;
auto flow = prGraph.getMaxFlow(s, t);

当然，你需要自己阅读所有的边和容量以及节点的数量，我希望这是一个起点。

int main()
{
   struct PushRelabel prGraph(4);
   prGraph.AddEdge(0,1,2);
   prGraph.AddEdge(0,2,2);
   prGraph.AddEdge(1,3,1);
   prGraph.AddEdge(2,3,3);

   std::cout<< prGraph.GetMaxFlow(0,3) << std::endl;
}

对于这个带有源s = 0和接收器的图t = 3

    1
   / \
c(2)  c(1)
 /     \
0       3
 \     /
c(2)  c(3)  
   \ /
    2

输出3，因为它应该。

于 2014-08-13T15:48:01.437 回答