Алгоритм Эдмондса-Карпа: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
Строка 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 | a(a), b(b), capacity(capacity) {} | ||
int other(int v) const { | int other(int v) const { | ||
Строка 14: | Строка 14: | ||
} | } | ||
void addFlowTo(int v, int | void addFlowTo(int v, int deltaFlow) { | ||
flow += (v == b ? | flow += (v == b ? deltaFlow : -deltaFlow); | ||
} | } | ||
}; | }; | ||
vector<Edge> edges; | vector<Edge> edges; | ||
vector<vector<int>> | vector<vector<int>> graph; | ||
vector<bool> visited; | vector<bool> visited; | ||
vector<int> edgeTo; | vector<int> edgeTo; | ||
void bfs(int | void bfs(int start) { | ||
queue<int> q; | queue<int> q; | ||
visited[ | visited[start] = 1; | ||
q.push( | q.push(start); | ||
while (!q.empty()) { | while (!q.empty()) { | ||
v = q.front(); | int v = q.front(); | ||
q.pop(); | q.pop(); | ||
for (int e : | 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 | bool hasPath(int start, int finish) { | ||
visited.assign(visited.size(), 0); | |||
bfs( | bfs(start); | ||
return visited[ | return visited[finish]; | ||
} | } | ||
int bottleneckCapacity(int | int bottleneckCapacity(int start, int finish) { | ||
int bCapacity = 1e9; | int bCapacity = 1e9; | ||
for (int 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 | void addFlow(int start, int finish, int deltaFlow) { | ||
for (int v = | for (int v = finish; v != start; v = edges[edgeTo[v]].other(v)) | ||
edges[edgeTo[v]].addFlowTo(v, | edges[edgeTo[v]].addFlowTo(v, deltaFlow); | ||
} | } | ||
public: | public: | ||
Graph(int vertexCount) | Graph(int vertexCount) : | ||
graph(vertexCount), visited(vertexCount), edgeTo(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)); | ||
graph[from].push_back(edges.size() - 1); | |||
graph[to].push_back(edges.size() - 1); | |||
} | } | ||
long long maxFlow(int | long long maxFlow(int start, int finish) { | ||
long long flow = 0; | long long flow = 0; | ||
while (hasPath( | while (hasPath(start, finish)) { | ||
int deltaFlow = bottleneckCapacity( | int deltaFlow = bottleneckCapacity(start, finish); | ||
addFlow( | addFlow(start, finish, deltaFlow); | ||
flow += deltaFlow; | flow += deltaFlow; | ||
} | } |
Текущая версия от 00:59, 3 января 2023
class Graph { struct Edge { int a, b, capacity, flow = 0; Edge(int a, int b, int capacity) : a(a), b(b), capacity(capacity) {} int other(int v) const { return v == a ? b : a; } int capacityTo(int v) const { return v == b ? capacity - flow : flow; } void addFlowTo(int v, int deltaFlow) { flow += (v == b ? deltaFlow : -deltaFlow); } }; vector<Edge> edges; vector<vector<int>> graph; vector<bool> visited; vector<int> edgeTo; void bfs(int start) { queue<int> q; visited[start] = 1; q.push(start); while (!q.empty()) { int v = q.front(); q.pop(); for (int e : graph[v]) { int to = edges[e].other(v); if (!visited[to] && edges[e].capacityTo(to)) { edgeTo[to] = e; visited[to] = 1; q.push(to); } } } } bool hasPath(int start, int finish) { visited.assign(visited.size(), 0); bfs(start); return visited[finish]; } int bottleneckCapacity(int start, int finish) { int bCapacity = 1e9; for (int v = finish; v != start; v = edges[edgeTo[v]].other(v)) bCapacity = min(bCapacity, edges[edgeTo[v]].capacityTo(v)); return bCapacity; } void addFlow(int start, int finish, int deltaFlow) { for (int v = finish; v != start; v = edges[edgeTo[v]].other(v)) edges[edgeTo[v]].addFlowTo(v, deltaFlow); } public: Graph(int vertexCount) : graph(vertexCount), visited(vertexCount), edgeTo(vertexCount) {} void addEdge(int from, int to, int capacity) { edges.push_back(Edge(from, to, capacity)); graph[from].push_back(edges.size() - 1); graph[to].push_back(edges.size() - 1); } long long maxFlow(int start, int finish) { long long flow = 0; while (hasPath(start, finish)) { int deltaFlow = bottleneckCapacity(start, finish); addFlow(start, finish, deltaFlow); flow += deltaFlow; } return flow; } };
Ссылки
Теория:
- algs4.cs.princeton.edu — 6.4 Maximum Flow
- e-maxx.ru — Алгоритм Эдмондса-Карпа нахождения максимального потока за O (NM^2)
- neerc.ifmo.ru/wiki — Алгоритм Эдмондса-Карпа
- Brilliant.org — Edmonds-Karp Algorithm
Демонстрация:
Код:
- CodeLibrary — Maximum flow. Edmonds-Karp algorithm in O(min(E^2 * V, E * FLOW))
- algs4.cs.princeton.edu/code — capacitated edge with flow, capacitated network, maxflow–mincut (несмотря на название, используется алгоритм Эдмондса-Карпа)
Задачи: