Алгоритм Диница - История изменений

Ctrlalt в 19:51, 22 октября 2025

2025-10-22T19:51:47Z

← Предыдущая версия		Версия от 19:51, 22 октября 2025
Строка 7:		Строка 7:

	int other(int v) const {		int other(int v) const {
	return v == a ? b ~~: a~~;		return v == b ? a : b;
	}		}

Строка 23:		Строка 23:
	vector<int> dist, edgeTo, index;		vector<int> dist, edgeTo, index;

	bool ~~bfs~~(int start, int finish) {		bool hasPath(int start, int finish) {
	dist.assign(graph.size(), 1e9);		dist.assign(graph.size(), 1e9);
			edgeTo.assign(graph.size(), -1);
			index.assign(graph.size(), 0);
	queue<int> q;		queue<int> q;

Строка 34:		Строка 36:
	q.pop();		q.pop();

	for (int e : graph[v]) {		for (int edgeIndex : graph[v]) {
	int to = edges[e].other(v);		int to = edges[edgeIndex].other(v);
	if (~~edges[e].capacityTo(to) &&~~ dist[to] > dist[v] + 1) {		if (dist[to] > dist[v] + 1 && edges[edgeIndex].capacityTo(to)) {
	dist[to] = dist[v] + 1;		dist[to] = dist[v] + 1;
	q.push(to);		q.push(to);
Строка 50:		Строка 52:
	return 1;		return 1;

	for ( ; index[v] < graph[v].size(); index[v]++) {		for (; index[v] < graph[v].size(); index[v]++) {
	int e = graph[v][index[v]], to = edges[e].other(v);		int edgeIndex = graph[v][index[v]], to = edges[edgeIndex].other(v);
	if (~~edges[e].capacityTo(to) &&~~ dist[to] == dist[v] + 1 && dfs(to, finish)) {		if (dist[to] == dist[v] + 1 && edges[edgeIndex].capacityTo(to) && dfs(to, finish)) {
	edgeTo[to] = e;		edgeTo[to] = edgeIndex;
	return 1;		return 1;
	}		}
Строка 61:		Строка 63:
	}		}

	int ~~bottleneckCapacity~~(int start, int finish) {		int getMinCapacity(int start, int finish) {
	int ~~bCapacity~~ = 1e9;		int minCapacity = 1e9;
	for (int v = finish; v != start; 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));		minCapacity = min(minCapacity, edges[edgeTo[v]].capacityTo(v));
	return ~~bCapacity~~;		return minCapacity;
	}		}

Строка 74:		Строка 76:

	public:		public:
	Graph(int vertexCount) :		Graph(int vertexCount) : graph(vertexCount) {}
	graph~~(vertexCount), dist(vertexCount), edgeTo(vertexCount), index~~(vertexCount) {}

	void addEdge(int from, int to, int capacity) {		void addEdge(int from, int to, int capacity) {
Строка 85:		Строка 86:
	long long maxFlow(int start, int finish) {		long long maxFlow(int start, int finish) {
	long long flow = 0;		long long flow = 0;
	while (~~bfs~~(start, finish)) {		while (hasPath(start, finish)) {
	~~index.assign(graph.size(), 0);~~
	while (dfs(start, finish)) {		while (dfs(start, finish)) {
	int deltaFlow = ~~bottleneckCapacity~~(start, finish);		int deltaFlow = getMinCapacity(start, finish);
	addFlow(start, finish, deltaFlow);		addFlow(start, finish, deltaFlow);
	flow += deltaFlow;		flow += deltaFlow;

Ctrlalt: /* Ссылки */

2025-08-07T22:23:27Z

Ссылки

← Предыдущая версия		Версия от 22:23, 7 августа 2025
Строка 104:		Строка 104:
	* [https://wiki.algocode.ru/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B8%D0%BD%D0%B8%D1%86%D0%B0 wiki.algocode.ru — Алгоритм Диница]		* [https://wiki.algocode.ru/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B8%D0%BD%D0%B8%D1%86%D0%B0 wiki.algocode.ru — Алгоритм Диница]
	* [https://codeforces.com/blog/entry/104960 codeforces.com — My way of understanding Dinic's algorithm]		* [https://codeforces.com/blog/entry/104960 codeforces.com — My way of understanding Dinic's algorithm]
			* [https://codeforces.com/blog/entry/145343 codeforces.com — Worst-Case Graphs for Maximum Flow Algorithms]
	* [https://usaco.guide/adv/max-flow?lang=cpp#dinics-algorithm usaco.guide — Dinic's Algorithm]		* [https://usaco.guide/adv/max-flow?lang=cpp#dinics-algorithm usaco.guide — Dinic's Algorithm]
	Демонстрация:		Демонстрация:

Ctrlalt в 00:59, 3 января 2023

2023-01-03T00:59:05Z

← Предыдущая версия		Версия от 00:59, 3 января 2023
Строка 6:		Строка 6:
	a(a), b(b), capacity(capacity) {}		a(a), b(b), capacity(capacity) {}

	int other(int v) {		int other(int v) const {
	return v == a ? b : a;		return v == a ? b : a;
	}		}

	int capacityTo(int v) {		int capacityTo(int v) const {
	return v == b ? capacity - flow : flow;		return v == b ? capacity - flow : flow;
	}		}

Ctrlalt в 11:45, 20 ноября 2022

2022-11-20T11:45:51Z

Внесённые изменения

Ctrlalt: Новая страница: « #include #include #include #include using namespace std; struct Edge { int a, b, cap, flow; Edge(int a, i…»

2015-05-27T22:32:25Z

Новая страница: « #include <stdio.h> #include <algorithm> #include <vector> #include <queue> using namespace std; struct Edge { int a, b, cap, flow; Edge(int a, i…»

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

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

struct Edge {
int a, b, cap, flow;
Edge(int a, int b, int cap) : a(a), b(b), cap(cap), flow(0) {}
int other(int v) {
return v == a ? b : a;
}
int capTo(int v) {
return v == b ? cap - flow : flow;
}
void addFlowTo(int v, int f) {
flow += (v == b ? f : -f);
}
};
vector<Edge> edges;

int n, m, u[1010], p[1010], pos[1010];
vector<int> g[1010];

bool bfs(int v, int vTarget) {
queue<int> q;
u[v] = 1;
q.push(v);
while (!q.empty()) {
v = q.front();
q.pop();
if (v == vTarget)
return 1;
for (int i = 0; i < g[v].size(); i++) {
int e = g[v][i], to = edges[e].other(v);
if (!u[to] && edges[e].capTo(to)) {
p[to] = e;
u[to] = u[v] + 1;
q.push(to);
}
}
}
return 0;
}

bool dfs(int v, int vTarget) {
if (v == vTarget)
return 1;
for (; pos[v] < g[v].size(); pos[v]++) {
int e = g[v][pos[v]], to = edges[e].other(v);
if (u[v] + 1 == u[to] && edges[e].capTo(to)) {
p[to] = e;
if (dfs(to, vTarget))
return 1;
}
}
return 0;
}

int main() {
scanf("%d%d", &n, &m);
int a, b, cap;
for (int i = 0; i < m; i++) {
scanf("%d%d%d", &a, &b, &cap);
edges.push_back(Edge(a - 1, b - 1, cap));
g[a - 1].push_back(edges.size() - 1);
g[b - 1].push_back(edges.size() - 1);
}

int flow = 0;
while (1) {
fill(u, u + n, 0);
if (!bfs(0, n - 1))
break;
fill(pos, pos + n, 0);
while (dfs(0, n - 1)) {
int deltaFlow = 1 << 30;
for (int v = n - 1; v != 0; v = edges[p[v]].other(v))
deltaFlow = min(deltaFlow, edges[p[v]].capTo(v));
flow += deltaFlow;
for (int v = n - 1; v != 0; v = edges[p[v]].other(v))
edges[p[v]].addFlowTo(v, deltaFlow);
}
}
printf("%d", flow);
}

== Ссылки ==
* [http://e-maxx.ru/algo/dinic e-maxx.ru — Алгоритм Диница нахождения максимального потока]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D1%85%D0%B5%D0%BC%D0%B0_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B0_%D0%94%D0%B8%D0%BD%D0%B8%D1%86%D0%B0 neerc.ifmo.ru/wiki — Схема алгоритма Диница]
* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 9]
* [http://github.com/indy256/codelibrary/blob/master/java/src/MaxFlowDinic.java CodeLibrary — Dinic's algorithm in O(V^2 * E)]
* [http://github.com/ADJA/algos/blob/master/Graphs/Dinic.cpp Algos — MaxFlow Dinic algorithm with scaling. O(N * M * log(MC))]
* [http://visualgo.net/maxflow.html VisuAlgo — Network Flow]

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