Максимальный поток минимальной стоимости - История изменений

Ctrlalt в 17:51, 25 июня 2023

2023-06-25T17:51:26Z

← Предыдущая версия		Версия от 17:51, 25 июня 2023
Строка 1:		Строка 1:
	class Edge {		class Graph {
	int _a, _b, capacity, flow, cost;		struct Edge {
	~~public:~~		int a, b, capacity, flow = 0, cost;
	Edge(int a, int b, int capacity, int cost) : _a(a), _b(b), capacity(capacity~~), flow(0~~), cost(cost) {}
	~~int a() const {~~		Edge(int a, int b, int capacity, int cost) :
	~~return _a;~~		a(a), b(b), capacity(capacity), cost(cost) {}
	}
	~~int b() const {~~		int other(int v) const {
	~~return _b;~~		return v == a ? b : a;
	}		}
	int other(int v) const {
	return v == _a ? _b : _a;		int capacityTo(int v) const {
	}		return v == b ? capacity - flow : flow;
	int capacityTo(int v) const {		}
	return v == _b ? capacity - flow : flow;
	}		int costTo(int v) const {
	int costTo(int v) const {		return v == b ? cost : -cost;
	return v == _b ? cost : -cost;		}
	}
	void addFlowTo(int v, int f) {		void addFlowTo(int v, int deltaFlow) {
	flow += (v == _b ? f : -f);		flow += (v == b ? deltaFlow : -deltaFlow);
	}		}
	};		};

	~~class Graph {~~
	vector<Edge> edges;		vector<Edge> edges;
	vector<int> distTo;		vector<int> distTo;
	vector<int> edgeTo;		vector<int> edgeTo;
	static const int INF = ~~1 << 30~~;		static const int INF = 1e9;
	void fordBellman(int v) {
			void fordBellman(int start) {
			fill(distTo.begin(), distTo.end(), INF);
			distTo[start] = 0;
	while (1) {		while (1) {
	bool update = 0;		bool update = 0;
	for (int i = 0; i < edges.size(); i++) {		for (int i = 0; i < edges.size(); i++) {
	int a = edges[i].a(), b = edges[i].b();		int a = edges[i].a, b = edges[i].b;
	if (edges[i].capacityTo(b) && distTo[a] != INF && distTo[b] > distTo[a] + edges[i].costTo(b)) {		if (edges[i].capacityTo(b) && distTo[a] != INF && distTo[b] > distTo[a] + edges[i].costTo(b)) {
	distTo[b] = distTo[a] + edges[i].costTo(b);		distTo[b] = distTo[a] + edges[i].costTo(b);
Строка 48:		Строка 50:
	}		}
	}		}
	bool hasPath(int ~~from~~, int to) {
	~~fill(distTo.begin(), distTo.end(), INF);~~		bool hasPath(int start, int finish) {
	~~distTo[from] = 0;~~		fordBellman(start);
	fordBellman(~~from~~);		return distTo[finish] != INF;
	return distTo[to] != INF;
	}		}
	int bottleneckCapacity(int ~~from~~, int to) {
			int bottleneckCapacity(int start, int finish) {
	int bCapacity = INF;		int bCapacity = INF;
	for (int v = to; v != ~~from~~; v = edges[edgeTo[v]].other(v))		for (int v = finish; v != start; v = edges[edgeTo[v]].other(v))
	bCapacity = min(bCapacity, edges[edgeTo[v]].capacityTo(v));		bCapacity = min(bCapacity, edges[edgeTo[v]].capacityTo(v));
	return bCapacity;		return bCapacity;
	}		}
	long long addFlow(int ~~from~~, int to, int ~~flow~~) {
			long long addFlow(int start, int finish, int deltaFlow) {
	long long deltaCost = 0;		long long deltaCost = 0;
	for (int v = to; v != ~~from~~; v = edges[edgeTo[v]].other(v)) {		for (int v = finish; v != start; v = edges[edgeTo[v]].other(v)) {
	edges[edgeTo[v]].addFlowTo(v, ~~flow~~);		edges[edgeTo[v]].addFlowTo(v, deltaFlow);
	deltaCost += ~~flow~~ * edges[edgeTo[v]].costTo(v);		deltaCost += deltaFlow * edges[edgeTo[v]].costTo(v);
	}		}
	return deltaCost;		return deltaCost;
	}		}

	public:		public:
	Graph(int ~~verticesCount~~) {		Graph(int vertexCount) :
	distTo~~.resize~~(~~verticesCount~~);		distTo(vertexCount), edgeTo(vertexCount) {}
	edgeTo~~.resize~~(~~verticesCount~~);
	}
	void addEdge(int from, int to, int capacity, int cost) {		void addEdge(int from, int to, int capacity, int cost) {
	edges.push_back(Edge(from, to, capacity, cost));		edges.push_back(Edge(from, to, capacity, cost));
	}		}
	pair<long long, long long> minCostMaxFlow(int ~~from~~, int to) {
			pair<long long, long long> minCostMaxFlow(int start, int finish) {
	long long cost = 0, flow = 0;		long long cost = 0, flow = 0;
	while (hasPath(~~from~~, to)) {		while (hasPath(start, finish)) {
	int deltaFlow = bottleneckCapacity(~~from~~, to);		int deltaFlow = bottleneckCapacity(start, finish);
	cost += addFlow(~~from~~, to, deltaFlow);		cost += addFlow(start, finish, deltaFlow);
	flow += deltaFlow;		flow += deltaFlow;
	}		}
	return ~~make_pair(~~cost, flow);		return { cost, flow };
	}		}
	};		};

Ctrlalt в 21:47, 6 августа 2016

2016-08-06T21:47:05Z

← Предыдущая версия		Версия от 21:47, 6 августа 2016
Строка 1:		Строка 1:
	~~#include <stdio.h>~~
	~~#include <algorithm>~~
	~~#include <vector>~~
	~~#include <queue>~~
	~~using namespace std;~~

	class Edge {		class Edge {
	int _a, _b, capacity, flow, cost;		int _a, _b, capacity, flow, cost;
Строка 33:		Строка 27:
	vector<int> distTo;		vector<int> distTo;
	vector<int> edgeTo;		vector<int> edgeTo;
			static const int INF = 1 << 30;
	void fordBellman(int v) {		void fordBellman(int v) {
	while (1) {		while (1) {
Строка 38:		Строка 33:
	for (int i = 0; i < edges.size(); i++) {		for (int i = 0; i < edges.size(); i++) {
	int a = edges[i].a(), b = edges[i].b();		int a = edges[i].a(), b = edges[i].b();
	if (edges[i].capacityTo(b) && distTo[b] > distTo[a] + edges[i].costTo(b)) {		if (edges[i].capacityTo(b) && distTo[a] != INF && distTo[b] > distTo[a] + edges[i].costTo(b)) {
	distTo[b] = distTo[a] + edges[i].costTo(b);		distTo[b] = distTo[a] + edges[i].costTo(b);
	edgeTo[b] = i;		edgeTo[b] = i;
	update = 1;		update = 1;
	}		}
	if (edges[i].capacityTo(a) && distTo[a] > distTo[b] + edges[i].costTo(a)) {		if (edges[i].capacityTo(a) && distTo[b] != INF && distTo[a] > distTo[b] + edges[i].costTo(a)) {
	distTo[a] = distTo[b] + edges[i].costTo(a);		distTo[a] = distTo[b] + edges[i].costTo(a);
	edgeTo[a] = i;		edgeTo[a] = i;
Строка 54:		Строка 49:
	}		}
	bool hasPath(int from, int to) {		bool hasPath(int from, int to) {
	fill(distTo.begin(), distTo.end(), ~~1 << 30~~);		fill(distTo.begin(), distTo.end(), INF);
	distTo[from] = 0;		distTo[from] = 0;
	fordBellman(from);		fordBellman(from);
	return distTo[to] != ~~1 << 30~~;		return distTo[to] != INF;
	}		}
	int bottleneckCapacity(int from, int to) {		int bottleneckCapacity(int from, int to) {
	int bCapacity = ~~1 << 30~~;		int bCapacity = INF;
	for (int v = to; v != from; v = edges[edgeTo[v]].other(v))		for (int v = to; v != from; v = edges[edgeTo[v]].other(v))
	bCapacity = min(bCapacity, edges[edgeTo[v]].capacityTo(v));		bCapacity = min(bCapacity, edges[edgeTo[v]].capacityTo(v));
Строка 91:		Строка 86:
	}		}
	};		};


	~~int main() {~~
	~~int n;~~
	~~scanf("%d", &n);~~
	~~Graph g(2 * n + 2);~~

	~~int source = 0;~~
	~~for (int i = 1; i <= n; i++)~~
	~~g.addEdge(source, i, 1, 0);~~

	~~int c;~~
	~~for (int i = 1; i <= n; i++) {~~
	~~for (int j = n + 1; j <= 2 * n; j++) {~~
	~~scanf("%d", &c);~~
	~~g.addEdge(i, j, 1, c);~~
	}
	}

	~~int sink = 2 * n + 1;~~
	~~for (int i = n + 1; i <= 2 * n; i++)~~
	~~g.addEdge(i, sink, 1, 0);~~

	~~printf("%lld", g.minCostMaxFlow(source, sink).first);~~
	}

	== Ссылки ==		== Ссылки ==

Ctrlalt: Новая страница: « #include #include #include #include using namespace std; class Edge { int _a, _b, capacity, flow, cost; publi…»

2016-08-05T20:51:37Z

Новая страница: « #include <stdio.h> #include <algorithm> #include <vector> #include <queue> using namespace std; class Edge { int _a, _b, capacity, flow, cost; publi…»

Новая страница

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

class Edge {
int _a, _b, capacity, flow, cost;
public:
Edge(int a, int b, int capacity, int cost) : _a(a), _b(b), capacity(capacity), flow(0), cost(cost) {}
int a() const {
return _a;
}
int b() const {
return _b;
}
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 f) {
flow += (v == _b ? f : -f);
}
};

class Graph {
vector<Edge> edges;
vector<int> distTo;
vector<int> edgeTo;
void fordBellman(int v) {
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) && distTo[b] > distTo[a] + edges[i].costTo(b)) {
distTo[b] = distTo[a] + edges[i].costTo(b);
edgeTo[b] = i;
update = 1;
}
if (edges[i].capacityTo(a) && distTo[a] > distTo[b] + edges[i].costTo(a)) {
distTo[a] = distTo[b] + edges[i].costTo(a);
edgeTo[a] = i;
update = 1;
}
}
if (!update)
break;
}
}
bool hasPath(int from, int to) {
fill(distTo.begin(), distTo.end(), 1 << 30);
distTo[from] = 0;
fordBellman(from);
return distTo[to] != 1 << 30;
}
int bottleneckCapacity(int from, int to) {
int bCapacity = 1 << 30;
for (int v = to; v != from; v = edges[edgeTo[v]].other(v))
bCapacity = min(bCapacity, edges[edgeTo[v]].capacityTo(v));
return bCapacity;
}
long long addFlow(int from, int to, int flow) {
long long deltaCost = 0;
for (int v = to; v != from; v = edges[edgeTo[v]].other(v)) {
edges[edgeTo[v]].addFlowTo(v, flow);
deltaCost += flow * edges[edgeTo[v]].costTo(v);
}
return deltaCost;
}
public:
Graph(int verticesCount) {
distTo.resize(verticesCount);
edgeTo.resize(verticesCount);
}
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 from, int to) {
long long cost = 0, flow = 0;
while (hasPath(from, to)) {
int deltaFlow = bottleneckCapacity(from, to);
cost += addFlow(from, to, deltaFlow);
flow += deltaFlow;
}
return make_pair(cost, flow);
}
};

int main() {
int n;
scanf("%d", &n);
Graph g(2 * n + 2);

int source = 0;
for (int i = 1; i <= n; i++)
g.addEdge(source, i, 1, 0);

int c;
for (int i = 1; i <= n; i++) {
for (int j = n + 1; j <= 2 * n; j++) {
scanf("%d", &c);
g.addEdge(i, j, 1, c);
}
}

int sink = 2 * n + 1;
for (int i = n + 1; i <= 2 * n; i++)
g.addEdge(i, sink, 1, 0);

printf("%lld", g.minCostMaxFlow(source, sink).first);
}

== Ссылки ==
Теория:
* [http://e-maxx.ru/algo/min_cost_flow_negative_cycles e-maxx.ru — Поток минимальной стоимости (min-cost-flow). Алгоритм увеличивающих путей]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B9_%D1%81%D1%82%D0%BE%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%B4%D0%BE%D0%BF%D0%BE%D0%BB%D0%BD%D0%B5%D0%BD%D0%B8%D1%8F_%D0%B2%D0%B4%D0%BE%D0%BB%D1%8C_%D0%BF%D1%83%D1%82%D0%B5%D0%B9_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B9_%D1%81%D1%82%D0%BE%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8 neerc.ifmo.ru/wiki — Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]
Код:
* [http://github.com/indy256/codelibrary/blob/master/java/src/MinCostFlowBF.java CodeLibrary — Maximum flow of minimum cost with Bellman–Ford]
* [http://github.com/indy256/codelibrary/blob/master/java/src/MinCostFlowDense.java CodeLibrary — Maximum flow of minimum cost with potentials for dense graphs]
* [http://github.com/indy256/codelibrary/blob/master/java/src/MinCostFlow.java CodeLibrary — Maximum flow of minimum cost with potentials]
* [http://github.com/ADJA/algos/blob/master/Graphs/MinCostFB.cpp Algos — Min Cost Flow (or Min Cost Max Flow) algorithm with Ford-Bellman algorithm as shortest path search method]
* [http://github.com/ADJA/algos/blob/master/Graphs/MinCostDijkstra.cpp 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))]
* [http://github.com/ADJA/algos/blob/master/Graphs/MinCostDijkstraHeap.cpp 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)]
Задачи:
* [[:Категория:Задачи: Максимальный поток минимальной стоимости|Задачи: Максимальный поток минимальной стоимости]]

[[Category: Максимальный поток]]