Максимальный поток минимальной стоимости
Перейти к навигации
Перейти к поиску
|
Через Форда-Беллмана class Graph {
struct Edge {
int a, b, capacity, flow = 0, cost;
Edge(int a, int b, int capacity, int cost) :
a(a), b(b), capacity(capacity), cost(cost) {}
int other(int v) const {
return v == a ? b : a;
}
int capacityTo(int v) const {
return v == b ? capacity - flow : flow;
}
int costTo(int v) const {
return v == b ? cost : -cost;
}
void addFlowTo(int v, int deltaFlow) {
flow += (v == b ? deltaFlow : -deltaFlow);
}
};
int vertexCount;
vector<Edge> edges;
vector<int> edgeTo;
bool hasPath(int start, int finish) {
vector<long long> dist(vertexCount, 1e18);
edgeTo.assign(vertexCount, -1);
dist[start] = 0;
while (1) {
bool update = 0;
for (int i = 0; i < edges.size(); i++) {
int a = edges[i].a, b = edges[i].b;
if (edges[i].capacityTo(b) && dist[a] != 1e18 && dist[b] > dist[a] + edges[i].costTo(b)) {
dist[b] = dist[a] + edges[i].costTo(b);
edgeTo[b] = i;
update = 1;
}
if (edges[i].capacityTo(a) && dist[b] != 1e18 && dist[a] > dist[b] + edges[i].costTo(a)) {
dist[a] = dist[b] + edges[i].costTo(a);
edgeTo[a] = i;
update = 1;
}
}
if (!update)
break;
}
return dist[finish] != 1e18;
}
int getMinCapacity(int start, int finish) {
int minCapacity = 1e9;
for (int v = finish; v != start; v = edges[edgeTo[v]].other(v))
minCapacity = min(minCapacity, edges[edgeTo[v]].capacityTo(v));
return minCapacity;
}
long long addFlow(int start, int finish, int deltaFlow) {
long long deltaCost = 0;
for (int v = finish; v != start; v = edges[edgeTo[v]].other(v)) {
edges[edgeTo[v]].addFlowTo(v, deltaFlow);
deltaCost += 1LL * deltaFlow * edges[edgeTo[v]].costTo(v);
}
return deltaCost;
}
public:
Graph(int vertexCount) : vertexCount(vertexCount) {}
void addEdge(int from, int to, int capacity, int cost) {
edges.push_back(Edge(from, to, capacity, cost));
}
pair<long long, long long> minCostMaxFlow(int start, int finish) {
long long cost = 0, flow = 0;
while (hasPath(start, finish)) {
int deltaFlow = getMinCapacity(start, finish);
cost += addFlow(start, finish, deltaFlow);
flow += deltaFlow;
}
return { cost, flow };
}
};
|
Через Джонсона class Graph {
struct Edge {
int a, b, capacity, flow = 0, cost;
Edge(int a, int b, int capacity, int cost) :
a(a), b(b), capacity(capacity), cost(cost) {}
int other(int v) const {
return v == a ? b : a;
}
int capacityTo(int v) const {
return v == b ? capacity - flow : flow;
}
int costTo(int v) const {
return v == b ? cost : -cost;
}
void addFlowTo(int v, int deltaFlow) {
flow += (v == b ? deltaFlow : -deltaFlow);
}
};
vector<Edge> edges;
vector<vector<int>> graph;
vector<long long> fordBellmanDist;
vector<int> edgeTo;
void initFordBellmanDist() {
fordBellmanDist.assign(graph.size(), 0);
while (1) {
bool update = 0;
for (Edge &edge : edges) {
int a = edge.a, b = edge.b;
if (edge.capacityTo(b) && fordBellmanDist[b] > fordBellmanDist[a] + edge.costTo(b)) {
fordBellmanDist[b] = fordBellmanDist[a] + edge.costTo(b);
update = 1;
}
if (edge.capacityTo(a) && fordBellmanDist[a] > fordBellmanDist[b] + edge.costTo(a)) {
fordBellmanDist[a] = fordBellmanDist[b] + edge.costTo(a);
update = 1;
}
}
if (!update)
break;
}
}
bool hasPath(int start, int finish) {
vector<long long> dist(graph.size(), 1e18);
edgeTo.assign(graph.size(), -1);
set<pair<long long, int>> q;
dist[start] = 0;
q.insert({ 0, start });
while (!q.empty()) {
int v = q.begin()->second;
q.erase(q.begin());
for (int edgeIndex : graph[v]) {
int to = edges[edgeIndex].other(v);
if (!edges[edgeIndex].capacityTo(to))
continue;
long long candidate = dist[v] + edges[edgeIndex].costTo(to) + fordBellmanDist[v] - fordBellmanDist[to];
if (dist[to] > candidate) {
q.erase({ dist[to], to });
dist[to] = candidate;
edgeTo[to] = edgeIndex;
q.insert({ dist[to], to });
}
}
}
if (dist[finish] == 1e18)
return 0;
for (int v = 0; v < graph.size(); v++)
if (dist[v] != 1e18)
fordBellmanDist[v] += dist[v];
return 1;
}
int getMinCapacity(int start, int finish) {
int minCapacity = 1e9;
for (int v = finish; v != start; v = edges[edgeTo[v]].other(v))
minCapacity = min(minCapacity, edges[edgeTo[v]].capacityTo(v));
return minCapacity;
}
long long addFlow(int start, int finish, int deltaFlow) {
long long deltaCost = 0;
for (int v = finish; v != start; v = edges[edgeTo[v]].other(v)) {
edges[edgeTo[v]].addFlowTo(v, deltaFlow);
deltaCost += 1LL * deltaFlow * edges[edgeTo[v]].costTo(v);
}
return deltaCost;
}
public:
Graph(int vertexCount) : graph(vertexCount) {}
void addEdge(int from, int to, int capacity, int cost) {
edges.push_back(Edge(from, to, capacity, cost));
graph[from].push_back(edges.size() - 1);
graph[to].push_back(edges.size() - 1);
}
pair<long long, long long> minCostMaxFlow(int start, int finish) {
initFordBellmanDist();
long long cost = 0, flow = 0;
while (hasPath(start, finish)) {
int deltaFlow = getMinCapacity(start, finish);
cost += addFlow(start, finish, deltaFlow);
flow += deltaFlow;
}
return { cost, flow };
}
};
|
Ссылки
Теория:
- e-maxx.ru — Поток минимальной стоимости (min-cost-flow). Алгоритм увеличивающих путей
- neerc.ifmo.ru/wiki — Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
Код:
- CodeLibrary — Maximum flow of minimum cost with Bellman–Ford
- CodeLibrary — Maximum flow of minimum cost with potentials for dense graphs
- CodeLibrary — Maximum flow of minimum cost with potentials
- Algos — Min Cost Flow (or Min Cost Max Flow) algorithm with Ford-Bellman algorithm as shortest path search method
- Algos — Min Cost Flow (or Min Cost Max Flow) algorithm with Dijkstra algorithm (with potentials) as shortest path search method. (Dijkstra for dense graphs running in O(N^2))
- Algos — Min Cost Flow (or Min Cost Max Flow) algorithm with Dijkstra algorithm (with potentials) as shortest path search method. (Dijkstra on heap for sparse graphs)
Задачи: