Я пытался понять этот код; это реализация алгоритма push-relbel в C ++:
// 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
следует использовать для инициализации некоторых Edge.from
с, и это должно быть похоже на sink
и немного Edge.to
с, но я не могу понять, как построить график.
Создать экземпляр структуры PushRelabel(N)
с N узлами:
struct PushRelabel prGraph(N);
Затем вы строите график с AddEdge
функция. Предполагая хорошую структуру Edge, это можно сделать как
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
, как это должно.