Алгоритм Эдмондса-Карпа - История изменений

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

2025-10-22T19:47:53Z

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

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

Строка 21:		Строка 21:
	vector<Edge> edges;		vector<Edge> edges;
	vector<vector<int>> graph;		vector<vector<int>> graph;
	vector<~~bool~~> visited;		vector<int> visited, edgeTo;
	~~vector<int>~~ edgeTo;

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

	visited[start] = 1;		visited[start] = 1;
	q.push(start);		q.push(start);

	while (!q.empty()) {		while (!q.empty()) {
	int v = q.front();		int v = q.front();
	q.pop();		q.pop();
	for (int e : graph[v]) {
	int to = edges[e].other(v);		for (int edgeIndex : graph[v]) {
	if (!visited[to] && edges[e].capacityTo(to)) {		int to = edges[edgeIndex].other(v);
	~~edgeTo[to] = e;~~		if (!visited[to] && edges[edgeIndex].capacityTo(to)) {
	visited[to] = 1;		visited[to] = 1;
			edgeTo[to] = edgeIndex;
	q.push(to);		q.push(to);
	}		}
	}		}
	}		}
	}

	~~bool hasPath(int start, int finish) {~~
	~~visited.assign(visited.size(), 0);~~
	~~bfs(start);~~
	return visited[finish];		return visited[finish];
	}		}

	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;
	}		}

Строка 61:		Строка 61:

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

	void addEdge(int from, int to, int capacity) {		void addEdge(int from, int to, int capacity) {
Строка 73:		Строка 72:
	long long flow = 0;		long long flow = 0;
	while (hasPath(start, finish)) {		while (hasPath(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:13Z

Ссылки

← Предыдущая версия		Версия от 22:23, 7 августа 2025
Строка 87:		Строка 87:
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%AD%D0%B4%D0%BC%D0%BE%D0%BD%D0%B4%D1%81%D0%B0-%D0%9A%D0%B0%D1%80%D0%BF%D0%B0 neerc.ifmo.ru/wiki — Алгоритм Эдмондса-Карпа]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%AD%D0%B4%D0%BC%D0%BE%D0%BD%D0%B4%D1%81%D0%B0-%D0%9A%D0%B0%D1%80%D0%BF%D0%B0 neerc.ifmo.ru/wiki — Алгоритм Эдмондса-Карпа]
	* [http://brilliant.org/wiki/edmonds-karp-algorithm Brilliant.org — Edmonds-Karp Algorithm]		* [http://brilliant.org/wiki/edmonds-karp-algorithm Brilliant.org — Edmonds-Karp Algorithm]
			* [https://codeforces.com/blog/entry/145343 codeforces.com — Worst-Case Graphs for Maximum Flow Algorithms]
	Демонстрация:		Демонстрация:
	* [https://visualgo.net/en/maxflow VisuAlgo — Network Flow]		* [https://visualgo.net/en/maxflow VisuAlgo — Network Flow]

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

2023-01-03T00:59:05Z

← Предыдущая версия		Версия от 00:59, 3 января 2023
Строка 1:		Строка 1:
	class Graph {		class Graph {
	struct Edge {		struct Edge {
	int a, b, capacity, flow;		int a, b, capacity, flow = 0;

	Edge(int a, int b, int capacity) :		Edge(int a, int b, int capacity) :
	a(a), b(b), capacity(capacity~~), flow(0~~) {}		a(a), b(b), capacity(capacity) {}

	int other(int v) const {		int other(int v) const {
Строка 14:		Строка 14:
	}		}

	void addFlowTo(int v, int f) {		void addFlowTo(int v, int deltaFlow) {
	flow += (v == b ? f : -f);		flow += (v == b ? deltaFlow : -deltaFlow);
	}		}
	};		};

	vector<Edge> edges;		vector<Edge> edges;
	vector<vector<int>> g;		vector<vector<int>> graph;
	vector<bool> visited;		vector<bool> visited;
	vector<int> edgeTo;		vector<int> edgeTo;

	void bfs(int v) {		void bfs(int start) {
	queue<int> q;		queue<int> q;
	visited[v] = 1;		visited[start] = 1;
	q.push(v);		q.push(start);
	while (!q.empty()) {		while (!q.empty()) {
	v = q.front();		int v = q.front();
	q.pop();		q.pop();
	for (int e : g[v]) {		for (int e : graph[v]) {
	int to = edges[e].other(v);		int to = edges[e].other(v);
	if (!visited[to] && edges[e].capacityTo(to)) {		if (!visited[to] && edges[e].capacityTo(to)) {
Строка 42:		Строка 42:
	}		}

	bool hasPath(int ~~from~~, int to) {		bool hasPath(int start, int finish) {
	~~fill(~~visited.~~begin~~(), visited.~~end~~(), 0);		visited.assign(visited.size(), 0);
	bfs(~~from~~);		bfs(start);
	return visited[to];		return visited[finish];
	}		}

	int bottleneckCapacity(int ~~from~~, int to) {		int bottleneckCapacity(int start, int finish) {
	int bCapacity = 1e9;		int bCapacity = 1e9;
	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;
	}		}

	void addFlow(int ~~from~~, int to, int ~~flow~~) {		void addFlow(int start, int finish, int deltaFlow) {
	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);
	}		}

	public:		public:
	Graph(int vertexCount) {		Graph(int vertexCount) :
	~~g.resize~~(vertexCount);		graph(vertexCount), visited(vertexCount), edgeTo(vertexCount) {}
	visited~~.resize~~(vertexCount);
	edgeTo~~.resize~~(vertexCount);
	}

	void addEdge(int from, int to, int capacity) {		void addEdge(int from, int to, int capacity) {
	edges.push_back(Edge(from, to, capacity));		edges.push_back(Edge(from, to, capacity));
	g[from].push_back(edges.size() - 1);		graph[from].push_back(edges.size() - 1);
	g[to].push_back(edges.size() - 1);		graph[to].push_back(edges.size() - 1);
	}		}

	long long maxFlow(int ~~from~~, int to) {		long long maxFlow(int start, int finish) {
	long long flow = 0;		long long flow = 0;
	while (hasPath(~~from~~, to)) {		while (hasPath(start, finish)) {
	int deltaFlow = bottleneckCapacity(~~from~~, to);		int deltaFlow = bottleneckCapacity(start, finish);
	addFlow(~~from~~, to, deltaFlow);		addFlow(start, finish, deltaFlow);
	flow += deltaFlow;		flow += deltaFlow;
	}		}

Ctrlalt в 02:48, 26 декабря 2021

2021-12-26T02:48:24Z

← Предыдущая версия		Версия от 02:48, 26 декабря 2021
Строка 1:		Строка 1:
	~~#include <stdio.h>~~		class Graph {
	~~#include <algorithm>~~		struct Edge {
	~~#include <vector>~~		int a, b, capacity, flow;
	~~#include <queue>~~
	~~using namespace std~~;		Edge(int a, int b, int capacity) :
			a(a), b(b), capacity(capacity), flow(0) {}

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

	~~class Edge {~~		int capacityTo(int v) const {
	~~int a, b, capacity, flow;~~		return v == b ? capacity - flow : flow;
	~~public:~~		}
	~~Edge(int a, int b, int capacity) : a(a), b(b), capacity(capacity), flow(0) {}~~
	~~int other(int v) const {~~		void addFlowTo(int v, int f) {
	~~return v == a ? b : a;~~		flow += (v == b ? f : -f);
	}		}
	int capacityTo(int v) const {		};
	return v == b ? capacity - flow : flow;
	}
	void addFlowTo(int v, int f) {
	flow += (v == b ? f : -f);
	}
	};

	~~class Graph {~~
	vector<Edge> edges;		vector<Edge> edges;
	vector<vector<int>> g;		vector<vector<int>> g;
	vector<bool> ~~used~~;		vector<bool> visited;
	vector<int> edgeTo;		vector<int> edgeTo;

	void bfs(int v) {		void bfs(int v) {
	queue<int> q;		queue<int> q;
	~~used~~[v] = 1;		visited[v] = 1;
	q.push(v);		q.push(v);
	while (!q.empty()) {		while (!q.empty()) {
Строка 34:		Строка 33:
	for (int e : g[v]) {		for (int e : g[v]) {
	int to = edges[e].other(v);		int to = edges[e].other(v);
	if (!~~used~~[to] && edges[e].capacityTo(to)) {		if (!visited[to] && edges[e].capacityTo(to)) {
	edgeTo[to] = e;		edgeTo[to] = e;
	~~used~~[to] = 1;		visited[to] = 1;
	q.push(to);		q.push(to);
	}		}
Строка 42:		Строка 41:
	}		}
	}		}

	bool hasPath(int from, int to) {		bool hasPath(int from, int to) {
	fill(~~used~~.begin(), ~~used~~.end(), 0);		fill(visited.begin(), visited.end(), 0);
	bfs(from);		bfs(from);
	return ~~used~~[to];		return visited[to];
	}		}

	int bottleneckCapacity(int from, int to) {		int bottleneckCapacity(int from, int to) {
	int bCapacity = 1e9;		int bCapacity = 1e9;
Строка 53:		Строка 54:
	return bCapacity;		return bCapacity;
	}		}

	void addFlow(int from, int to, int flow) {		void addFlow(int from, int to, int flow) {
	for (int v = to; v != from; v = edges[edgeTo[v]].other(v))		for (int v = to; v != from; v = edges[edgeTo[v]].other(v))
	edges[edgeTo[v]].addFlowTo(v, flow);		edges[edgeTo[v]].addFlowTo(v, flow);
	}		}

	public:		public:
	Graph(int ~~verticesCount~~) {		Graph(int vertexCount) {
	g.resize(~~verticesCount~~);		g.resize(vertexCount);
	~~used~~.resize(~~verticesCount~~);		visited.resize(vertexCount);
	edgeTo.resize(~~verticesCount~~);		edgeTo.resize(vertexCount);
	}		}

	void addEdge(int from, int to, int capacity) {		void addEdge(int from, int to, int capacity) {
	edges.push_back(Edge(from, to, capacity));		edges.push_back(Edge(from, to, capacity));
Строка 68:		Строка 72:
	g[to].push_back(edges.size() - 1);		g[to].push_back(edges.size() - 1);
	}		}

	long long maxFlow(int from, int to) {		long long maxFlow(int from, int to) {
	long long flow = 0;		long long flow = 0;
Строка 78:		Строка 83:
	}		}
	};		};


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

	~~int a, b, c;~~
	~~for (int i = 0; i < m; i++) {~~
	~~scanf("%d%d%d", &a, &b, &c);~~
	~~g.addEdge(a - 1, b - 1, c);~~
	}

	~~printf("%lld", g.maxFlow(0, n - 1));~~
	}

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

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

2020-09-22T23:13:44Z

Ссылки

← Предыдущая версия		Версия от 23:13, 22 сентября 2020
Строка 96:		Строка 96:
	== Ссылки ==		== Ссылки ==
	Теория:		Теория:
	* [~~http~~://algs4.cs.princeton.edu/lectures/64MaxFlow.pdf algs4.cs.princeton.edu~~/lectures —~~ 6.4 Maximum Flow]		* [https://algs4.cs.princeton.edu/lectures/keynote/64MaxFlow.pdf algs4.cs.princeton.edu — 6.4 Maximum Flow]
	* [http://e-maxx.ru/algo/edmonds_karp e-maxx.ru ~~—~~ Алгоритм Эдмондса-Карпа нахождения максимального потока за O (NM^2)]		* [http://e-maxx.ru/algo/edmonds_karp e-maxx.ru — Алгоритм Эдмондса-Карпа нахождения максимального потока за O (NM^2)]
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%AD%D0%B4%D0%BC%D0%BE%D0%BD%D0%B4%D1%81%D0%B0-%D0%9A%D0%B0%D1%80%D0%BF%D0%B0 neerc.ifmo.ru/wiki ~~—~~ Алгоритм Эдмондса-Карпа]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%AD%D0%B4%D0%BC%D0%BE%D0%BD%D0%B4%D1%81%D0%B0-%D0%9A%D0%B0%D1%80%D0%BF%D0%B0 neerc.ifmo.ru/wiki — Алгоритм Эдмондса-Карпа]
	* [http://brilliant.org/wiki/edmonds-karp-algorithm Brilliant.org — Edmonds-Karp Algorithm]		* [http://brilliant.org/wiki/edmonds-karp-algorithm Brilliant.org — Edmonds-Karp Algorithm]
	Демонстрация:		Демонстрация:
	* [~~http~~://visualgo.net/maxflow~~.html~~ VisuAlgo ~~—~~ Network Flow]		* [https://visualgo.net/en/maxflow VisuAlgo — Network Flow]
	Код:		Код:
	* [~~http~~://github.com/indy256/codelibrary/blob/master/java/~~src~~/MaxFlowEdmondsKarp.java CodeLibrary — Maximum flow. Edmonds-Karp algorithm in O(min(E^2 * V, E * FLOW))]		* [https://github.com/indy256/codelibrary/blob/master/java/graphs/flows/MaxFlowEdmondsKarp.java CodeLibrary — Maximum flow. Edmonds-Karp algorithm in O(min(E^2 * V, E * FLOW))]
	* algs4.cs.princeton.edu/code — [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/FlowEdge.java.html capacitated edge with flow], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/FlowNetwork.java.html capacitated network], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/FordFulkerson.java.html maxflow–mincut] (несмотря на название, используется алгоритм Эдмондса-Карпа)		* algs4.cs.princeton.edu/code — [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/FlowEdge.java.html capacitated edge with flow], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/FlowNetwork.java.html capacitated network], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/FordFulkerson.java.html maxflow–mincut] (несмотря на название, используется алгоритм Эдмондса-Карпа)
	Задачи:		Задачи:

Ctrlalt в 16:48, 15 февраля 2020

2020-02-15T16:48:23Z

← Предыдущая версия		Версия от 16:48, 15 февраля 2020
Строка 22:		Строка 22:
	class Graph {		class Graph {
	vector<Edge> edges;		vector<Edge> edges;
	vector< vector<int> > g;		vector<vector<int>> g;
	vector<bool> used;		vector<bool> used;
	vector<int> edgeTo;		vector<int> edgeTo;
Строка 32:		Строка 32:
	v = q.front();		v = q.front();
	q.pop();		q.pop();
	for (int ~~i = 0; i <~~ g[v]~~.size(); i++~~) {		for (int e : g[v]) {
	int ~~e = g[v][i],~~ to = edges[e].other(v);		int to = edges[e].other(v);
	if (!used[to] && edges[e].capacityTo(to)) {		if (!used[to] && edges[e].capacityTo(to)) {
	edgeTo[to] = e;		edgeTo[to] = e;
Строка 48:		Строка 48:
	}		}
	int bottleneckCapacity(int from, int to) {		int bottleneckCapacity(int from, int to) {
	int bCapacity = ~~1 << 30~~;		int bCapacity = 1e9;
	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));

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

2020-01-02T18:49:36Z

Ссылки

← Предыдущая версия		Версия от 18:49, 2 января 2020
Строка 99:		Строка 99:
	* [http://e-maxx.ru/algo/edmonds_karp e-maxx.ru — Алгоритм Эдмондса-Карпа нахождения максимального потока за O (NM^2)]		* [http://e-maxx.ru/algo/edmonds_karp e-maxx.ru — Алгоритм Эдмондса-Карпа нахождения максимального потока за O (NM^2)]
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%AD%D0%B4%D0%BC%D0%BE%D0%BD%D0%B4%D1%81%D0%B0-%D0%9A%D0%B0%D1%80%D0%BF%D0%B0 neerc.ifmo.ru/wiki — Алгоритм Эдмондса-Карпа]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%AD%D0%B4%D0%BC%D0%BE%D0%BD%D0%B4%D1%81%D0%B0-%D0%9A%D0%B0%D1%80%D0%BF%D0%B0 neerc.ifmo.ru/wiki — Алгоритм Эдмондса-Карпа]
			* [http://brilliant.org/wiki/edmonds-karp-algorithm Brilliant.org — Edmonds-Karp Algorithm]
	Демонстрация:		Демонстрация:
	* [http://visualgo.net/maxflow.html VisuAlgo — Network Flow]		* [http://visualgo.net/maxflow.html VisuAlgo — Network Flow]

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

2016-07-24T20:32:55Z

Ссылки

← Предыдущая версия		Версия от 20:32, 24 июля 2016
Строка 96:		Строка 96:
	== Ссылки ==		== Ссылки ==
	Теория:		Теория:
	:* [http://algs4.cs.princeton.edu/lectures/64MaxFlow.pdf algs4.cs.princeton.edu/lectures — 6.4 Maximum Flow]		* [http://algs4.cs.princeton.edu/lectures/64MaxFlow.pdf algs4.cs.princeton.edu/lectures — 6.4 Maximum Flow]
	:* [http://e-maxx.ru/algo/edmonds_karp e-maxx.ru — Алгоритм Эдмондса-Карпа нахождения максимального потока за O (NM^2)]		* [http://e-maxx.ru/algo/edmonds_karp e-maxx.ru — Алгоритм Эдмондса-Карпа нахождения максимального потока за O (NM^2)]
	:* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%AD%D0%B4%D0%BC%D0%BE%D0%BD%D0%B4%D1%81%D0%B0-%D0%9A%D0%B0%D1%80%D0%BF%D0%B0 neerc.ifmo.ru/wiki — Алгоритм Эдмондса-Карпа]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%AD%D0%B4%D0%BC%D0%BE%D0%BD%D0%B4%D1%81%D0%B0-%D0%9A%D0%B0%D1%80%D0%BF%D0%B0 neerc.ifmo.ru/wiki — Алгоритм Эдмондса-Карпа]
	Демонстрация:		Демонстрация:
	:* [http://visualgo.net/maxflow.html VisuAlgo — Network Flow]		* [http://visualgo.net/maxflow.html VisuAlgo — Network Flow]
	Код:		Код:
	:* [http://github.com/indy256/codelibrary/blob/master/java/src/MaxFlowEdmondsKarp.java CodeLibrary — Maximum flow. Edmonds-Karp algorithm in O(min(E^2 * V, E * FLOW))]		* [http://github.com/indy256/codelibrary/blob/master/java/src/MaxFlowEdmondsKarp.java CodeLibrary — Maximum flow. Edmonds-Karp algorithm in O(min(E^2 * V, E * FLOW))]
	:* algs4.cs.princeton.edu/code — [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/FlowEdge.java.html ~~FlowEdge~~], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/FlowNetwork.java.html ~~FlowNetwork~~], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/FordFulkerson.java.html ~~FordFulkerson~~] (несмотря на название, используется алгоритм Эдмондса-Карпа)		* algs4.cs.princeton.edu/code — [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/FlowEdge.java.html capacitated edge with flow], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/FlowNetwork.java.html capacitated network], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/FordFulkerson.java.html maxflow–mincut] (несмотря на название, используется алгоритм Эдмондса-Карпа)
	Задачи:		Задачи:
	:* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 9]		* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 9]
	:* [[:Категория:Задачи: Максимальный поток\|Задачи: Максимальный поток]]		* [[:Категория:Задачи: Максимальный поток\|Задачи: Максимальный поток]]

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

Ctrlalt в 19:58, 24 июля 2016

2016-07-24T19:58:56Z

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

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

2015-05-27T22:27:42Z

Ссылки

← Предыдущая версия		Версия от 22:27, 27 мая 2015
Строка 71:		Строка 71:
	== Ссылки ==		== Ссылки ==
	* [http://algs4.cs.princeton.edu/lectures/64MaxFlow.pdf algs4.cs.princeton.edu/lectures — 6.4 Maximum Flow]		* [http://algs4.cs.princeton.edu/lectures/64MaxFlow.pdf algs4.cs.princeton.edu/lectures — 6.4 Maximum Flow]
	* [http://e-maxx.ru/algo/edmonds_karp ~~emaxx~~.ru — Алгоритм Эдмондса-Карпа нахождения максимального потока за O (NM^2)]		* [http://e-maxx.ru/algo/edmonds_karp e-maxx.ru — Алгоритм Эдмондса-Карпа нахождения максимального потока за O (NM^2)]
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%AD%D0%B4%D0%BC%D0%BE%D0%BD%D0%B4%D1%81%D0%B0-%D0%9A%D0%B0%D1%80%D0%BF%D0%B0 neerc.ifmo.ru/wiki — Алгоритм Эдмондса-Карпа]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%AD%D0%B4%D0%BC%D0%BE%D0%BD%D0%B4%D1%81%D0%B0-%D0%9A%D0%B0%D1%80%D0%BF%D0%B0 neerc.ifmo.ru/wiki — Алгоритм Эдмондса-Карпа]
	* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 9]		* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 9]