Алгоритм Диница
Перейти к навигации
Перейти к поиску
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) {
return v == a ? b : a;
}
int capacityTo(int v) {
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<int> dist, edgeTo, index;
bool bfs(int start, int finish) {
dist.assign(graph.size(), 1e9);
queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int e : graph[v]) {
int to = edges[e].other(v);
if (edges[e].capacityTo(to) && dist[to] > dist[v] + 1) {
dist[to] = dist[v] + 1;
q.push(to);
}
}
}
return dist[finish] != 1e9;
}
bool dfs(int v, int finish) {
if (v == finish)
return 1;
for ( ; index[v] < graph[v].size(); index[v]++) {
int e = graph[v][index[v]], to = edges[e].other(v);
if (edges[e].capacityTo(to) && dist[to] == dist[v] + 1 && dfs(to, finish)) {
edgeTo[to] = e;
return 1;
}
}
return 0;
}
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), dist(vertexCount), edgeTo(vertexCount), index(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 (bfs(start, finish)) {
index.assign(graph.size(), 0);
while (dfs(start, finish)) {
int deltaFlow = bottleneckCapacity(start, finish);
addFlow(start, finish, deltaFlow);
flow += deltaFlow;
}
}
return flow;
}
};
Ссылки
Теория:
- e-maxx.ru — Алгоритм Диница нахождения максимального потока
- cp-algorithms.com — Maximum flow — Dinic's algorithm
- neerc.ifmo.ru/wiki — Схема алгоритма Диница
- wiki.algocode.ru — Алгоритм Диница
- codeforces.com — My way of understanding Dinic's algorithm
- usaco.guide — Dinic's Algorithm
Демонстрация:
Код:
Задачи: