Я не знаю, правильный ли алгоритм, но при условии, что код ссылки содержит несколько проблем.
- Использование заголовка
#include<bits/stdc++.h>.
- Утечки памяти.
Во-первых, следует избегать использования bits / stdc ++. H и использовать надлежащие #include файлы.
Во-вторых, использование std::vector устранит утечки памяти. Код использует std::vector в некоторых местах, но полностью отказывается использовать его в других местах. Например:
int *start = new int[V+1];
следует заменить на:
std::vector<int> start(V+1);
Первая вызывала утечку памяти из-за отсутствия delete [] start; в коде. При использовании std::vector утечка памяти исчезает.
Как только введено std::vector, в классе Graph, который отслеживает количество вершин, не требуется переменная-член V. Причина в том, что члены vector имеют размер V вершин, а vector уже знает свой собственный размер с помощью функции-члена vector::size(). Таким образом, переменная-член V является избыточной и может быть удалена.
Последнее изменение, которое можно сделать, - это переместиться на struct Edge в класс Graph.
Учитывая все упомянутые изменения, здесь приведена очищенная версия, которая возвращает тот же результат, что и исходный код, при запуске с графиком теста, установленным в функции main():
#include <vector>
#include <list>
#include <algorithm>
#include <iostream>
#include <climits>
class Graph
{
struct Edge
{
int v;
int flow;
int C;
int rev;
};
std::vector<int> level;
std::vector<std::vector< Edge >> adj;
public:
Graph(int V) : level(V), adj(V) {}
void addEdge(int u, int v, int C)
{
adj[u].push_back({ v, 0, C, static_cast<int>(adj[v].size()) });
adj[v].push_back({ u, 0, 0, static_cast<int>(adj[u].size()) });
}
bool BFS(int s, int t);
int sendFlow(int s, int flow, int t, std::vector<int>& ptr);
int DinicMaxflow(int s, int t);
};
bool Graph::BFS(int s, int t)
{
std::fill(level.begin(), level.end(), -1);
level[s] = 0;
std::list< int > q;
q.push_back(s);
std::vector<Edge>::iterator i;
while (!q.empty())
{
int u = q.front();
q.pop_front();
for (i = adj[u].begin(); i != adj[u].end(); i++)
{
Edge &e = *i;
if (level[e.v] < 0 && e.flow < e.C)
{
level[e.v] = level[u] + 1;
q.push_back(e.v);
}
}
}
return level[t] < 0 ? false : true;
}
int Graph::sendFlow(int u, int flow, int t, std::vector<int>& start)
{
if (u == t)
return flow;
for (; start[u] < static_cast<int>(adj[u].size()); start[u]++)
{
// Pick next edge from adjacency list of u
Edge &e = adj[u][start[u]];
if (level[e.v] == level[u] + 1 && e.flow < e.C)
{
int curr_flow = std::min(flow, e.C - e.flow);
int temp_flow = sendFlow(e.v, curr_flow, t, start);
if (temp_flow > 0)
{
e.flow += temp_flow;
adj[e.v][e.rev].flow -= temp_flow;
return temp_flow;
}
}
}
return 0;
}
int Graph::DinicMaxflow(int s, int t)
{
if (s == t)
return -1;
int total = 0;
while (BFS(s, t) == true)
{
std::vector<int> start(level.size() + 1);
while (int flow = sendFlow(s, INT_MAX, t, start))
total += flow;
}
return total;
}
Функция проверки выглядит следующим образом:
int main()
{
Graph g(6);
g.addEdge(0, 1, 16 );
g.addEdge(0, 2, 13 );
g.addEdge(1, 2, 10 );
g.addEdge(1, 3, 12 );
g.addEdge(2, 1, 4 );
g.addEdge(2, 4, 14);
g.addEdge(3, 2, 9 );
g.addEdge(3, 5, 20 );
g.addEdge(4, 3, 7 );
g.addEdge(4, 5, 4);
std::cout << "Maximum flow " << g.DinicMaxflow(0, 5);
}
Живой пример
Теперь, если вы хотите посмотреть, что произойдет, если вы используете double вместо int в качестве величины потока, проще всего создать класс шаблона на основе приведенного выше кода. Цель состоит в том, чтобы взять, где используется int, и вместо замены int на double заменить int параметром шаблона (например, T). Полученный код будет выглядеть следующим образом:
#include <vector>
#include <list>
#include <algorithm>
#include <iostream>
#include <climits>
template <typename T>
class Graph
{
struct Edge
{
int v;
T flow;
T C;
int rev;
};
std::vector<int> level;
std::vector<std::vector<Edge>> adj;
public:
Graph(int V) : level(V), adj(V) {}
void addEdge(int u, int v, T C)
{
adj[u].push_back({ v, T(), C, static_cast<int>(adj[v].size())});
adj[v].push_back({ u, T(), T(), static_cast<int>(adj[u].size())}); // reverse edge
}
bool BFS(int s, int t);
T sendFlow(int s, T flow, int t, std::vector<int>& ptr);
T DinicMaxflow(int s, int t);
};
template <typename T>
bool Graph<T>::BFS(int s, int t)
{
std::fill(level.begin(), level.end(), -1);
level[s] = 0;
std::list< int > q;
q.push_back(s);
typename std::vector<Edge>::iterator i;
while (!q.empty())
{
int u = q.front();
q.pop_front();
for (i = adj[u].begin(); i != adj[u].end(); i++)
{
Edge &e = *i;
if (level[e.v] < 0 && e.flow < e.C)
{
level[e.v] = level[u] + 1;
q.push_back(e.v);
}
}
}
return level[t] < 0 ? false : true;
}
template <typename T>
T Graph<T>::sendFlow(int u, T flow, int t, std::vector<int>& start)
{
if (u == t)
return flow;
for (; start[u] < static_cast<int>(adj[u].size()); start[u]++)
{
Edge &e = adj[u][start[u]];
if (level[e.v] == level[u] + 1 && e.flow < e.C)
{
T curr_flow = std::min(flow, e.C - e.flow);
T temp_flow = sendFlow(e.v, curr_flow, t, start);
if (temp_flow > 0)
{
e.flow += temp_flow;
adj[e.v][e.rev].flow -= temp_flow;
return temp_flow;
}
}
}
return 0;
}
template <typename T>
T Graph<T>::DinicMaxflow(int s, int t)
{
if (s == t)
return -1;
T total = 0;
while (BFS(s, t) == true)
{
std::vector<int> start(level.size() + 1);
while (T flow = sendFlow(s, INT_MAX, t, start))
total += flow;
}
return total;
}
Живой пример
Тестовый пример main будет состоять в том, чтобы просто использовать Graph<double> или Graph<int> вместо простого Graph - все остальное в функции main остается прежним.
Теперь, когда функция является шаблоном, любой числовой тип, который поддерживает те же операции, что и int или double, можно легко заменить, просто создав Graph<numerical_type>.