E060. Thuật toán Диница
Источник: e-maxx.ru/algo, страница PDF 178.
Постановка задачи
Пусть дана сеть, т.е. ориентированный đồ thị
, в котором каждому ребру
приписана пропускная способность
, а также выделены две вершины — исток
и сток
.
it is required find в этой сети поток
из истока
в сток
максимальной величины.
Немного истории
Этот Thuật toán был опубликован советским (израильским) учёным Ефимом Диницем (Yefim Dinic, иногда пишется как "Dinitz") в 1970 г., т.е. даже на два года раньше опубликования Thuật toánа Эдмондса-Карпа (впрочем, оба Thuật toánа были независимо открыты в 1968 г.). Кроме того, следует отметить, что некоторые упрощения Thuật toánа были произведены Шимоном Ивеном (Shimon Even) и его учеником Алоном Итаи (Alon Itai) в 1979 г. Именно благодаря им Thuật toán получил свой современный облик: они применили к идее Диница концепцию блокирующих потоков Александра Карзанова (Alexander Karzanov, 1974 г.), а также переформулировали Thuật toán к той комбинации обхода в ширину и в глубину, в которой сейчас этот Thuật toán и излагается везде. Развитие идей по отношению к потоковым Thuật toánам крайне интересно рассматривать, given "железный занавес" тех лет, разделявший СССР и Запад. Видно, как иногда похожие идеи появлялись почти одновременно (как в случае Thuật toánа Диница и Thuật toánа Эдмондса-Карпа), правда, имея при этом разную эффективность (Thuật toán Диница на один порядок быстрее); иногда же, наоборот, появление идеи по одну сторону "занавеса" опережало аналогичный ход по другую сторону более чем на десятилетие (как Thuật toán Карзанова проталкивания в 1974 г. и Thuật toán Гольдберга (Goldberg) проталкивания в 1985 г.).
Необходимые определения
Введём три необходимых определения (каждое из них является независимым от остальных), которые затем будут использоваться в Thuật toánе Диница.
Остаточной сетью
по отношению к сети
и некоторому потоку
в ней называется сеть, в которой
каждому ребру
с пропускной способностью
и потоком
соответствуют два ребра:
●
с пропускной способностью
●
с пропускной способностью
Стоит отметить, что при таком определении в остаточной сети могут появляться кратные рёбра: если в исходной
сети было как edge
, так и
. Остаточное edge можно интуитивно понимать как меру того, насколько ещё можно увеличить поток вдоль какого-то
ребра. В самом деле, если по ребру
с пропускной способностью
протекает поток
, то потенциально
по нему можно пропустить ещё
единиц потока, а в обратную сторону можно пропустить до
единиц потока, что будет означать отмену потока в первоначальном направлении. Блокирующим потоком в данной сети называется такой поток, что любой путь из истока
в сток
содержит насыщенное этим потоком edge. Иными словами, в данной сети не найдётся такого пути из истока в сток, вдоль которого можно беспрепятственно увеличить поток. Блокирующий поток не обязательно максимален. Теорема Форда-Фалкерсона говорит о том, что поток будет максимальным тогда и только тогда, когда в остаточной сети не найдётся
пути; в блокирующем же
потоке ничего не утверждается о существовании пути по рёбрам, появляющимся в остаточной сети. Слоистая сеть для данной сети строится следующим образом. Сначала определяются длины кратчайших путей
из истока
до всех остальных вершин; назовём уровнем
вершины её расстояние от истока. Тогда в
слоистую сеть включают все те рёбра
исходной сети, которые ведут с одного уровня на какой-либо другой, более поздний, уровень, т.е.
(почему в этом случае разница расстояний не
может превосходить единицы, следует из свойства кратчайших расстояний). Таким образом, удаляются все рёбра, расположенные целиком внутри уровней, а также рёбра, ведущие назад, к предыдущим уровням.
Очевидно, слоистая сеть ациклична. Кроме того, любой
путь в слоистой сети является кратчайшим путём
в исходной сети. Построить слоистую сеть по данной сети очень легко: для этого надо запустить обход в ширину по рёбрам этой
сети, посчитав тем самым для каждой вершины величину
, и затем внести в слоистую сеть все подходящие рёбра. Примечание. Термин "слоистая сеть" в русскоязычной литературе не употребляется; обычно эта конструкция называется просто "вспомогательным đồ thịом". Впрочем, на английском языке обычно используется термин "layered network".
Thuật toán
Схема Thuật toánа
Thuật toán представляет собой несколько фаз. На каждой фазе сначала строится остаточная сеть, затем по отношению к ней строится слоистая сеть (обходом в ширину), а в ней ищется произвольный блокирующий поток. Найденный блокирующий поток прибавляется к текущему потоку, и на этом очередная итерация заканчивается. Этот Thuật toán схож с Thuật toánом Эдмондса-Карпа, но основное отличие можно понимать так: на каждой итерации
поток увеличивается не вдоль одного кратчайшего
пути, а вдоль целого набора таких путей (ведь именно
такими путями и являются пути в блокирующем потоке слоистой сети).
Корректность Thuật toánа
Покажем, что если Thuật toán завершается, то на Đầu raе у него получается поток именно максимальной величины. В самом деле, предположим, что в какой-то момент в слоистой сети, построенной для остаточной сети, не удалось
find блокирующий поток. Это означает, что сток
вообще не достижим в слоистой сети из истока
. Но
поскольку слоистая сеть содержит в себе все кратчайшие пути из истока в остаточной сети, это в свою очередь означает, что в остаточной сети нет пути из истока в сток. Следовательно, применяя теорему Форда- Фалкерсона, получаем, что текущий поток в самом деле максимален.
Оценка числа фаз
Покажем, что Thuật toán Диница всегда выполняет менее
фаз. Для этого докажем две леммы: Лемма 1. Кратчайшее расстояние от истока до каждой вершины не уменьшается с выполнением каждой итерации, т.е. где нижний индекс обозначает номер фазы, перед которой взяты значения этих переменных.
Chứng minh. Зафиксируем произвольную фазу
и произвольную вершину
и рассмотрим любой
кратчайший
путь
в сети
(напомним, так мы обозначаем остаточную сеть, взятую перед
выполнением
-ой фазы). Очевидно, длина пути
равна
.
Заметим, что в остаточную сеть
могут Đầu vàoить только рёбра из
, а также рёбра, обратные рёбрам из
(это следует из определения остаточной сети). Рассмотрим два случая:
● Путь
содержит только рёбра из
. Тогда, понятно, длина пути
больше либо равна
(потому
что
по определению — длина кратчайшего пути), что и означает выполнение неравенства.
● Путь
содержит как минимум одно edge, не содержащееся в
(но обратное какому-то ребру из
).
Рассмотрим первое такое edge; пусть это будет edge
.
Мы можем применить нашу лемму к вершине
, потому что она подпадает под первый случай; итак, мы
получаем неравенство
.
Теперь заметим, что поскольку edge
появилось в остаточной сети только после выполнения
-ой фазы,
то отсюда следует, что вдоль ребра
был дополнительно пропущен какой-то поток; следовательно, edge
принадлежало слоистой сети перед
-ой фазой, а потому
. Учтём, что
по свойству кратчайших путей
, и объединяя это равенство с двумя
предыдущими неравенствами, получаем: Теперь мы можем применять те же самые рассуждения ко всему оставшемуся пути до
(т.е. что каждое
инвертированное edge добавляет к
как минимум два), и в итоге получим требуемое неравенство. Лемма 2. Расстояние между истоком и стоком строго увеличивается после каждой фазы Thuật toánа, т.е.: где штрихом помечено значение, полученное на следующей фазе Thuật toánа. Chứng minh: от противного. Предположим, что после выполнения текущей фазы оказалось,
что
. Рассмотрим đường đi ngắn nhất из истока в сток; по предположению, его длина должна сохраниться неизменной. Однако остаточная сеть на следующей фазе содержит только рёбра остаточной сети перед выполнением текущей фазы, либо обратные к ним. Таким образом, пришли к противоречию: нашёлся путь, который не содержит насыщенных рёбер, и имеет ту же длину, что и đường đi ngắn nhất. Этот путь должен был быть "заблокирован" блокирующим потоком, чего не произошло, в чём и заключается противоречие, что и требовалось доказать.
Эту лемму интуитивно можно понимать следующим образом: на
-ой фазе Thuật toán Диница выявляет и насыщает
все
пути длины
.
Поскольку длина кратчайшего пути из
в
не может превосходить
, то, следовательно, Thuật toán
Диница совершает не более
фазы.
Поиск блокирующего потока
Чтобы завершить построение Thuật toánа Диница, надо описать Thuật toán нахождения блокирующего потока в слоистой сети — ключевое место Thuật toánа. Мы рассмотрим три возможных варианта реализации поиска блокирующего потока:
● Искать
пути по одному, пока такие пути находятся. Путь можно find за
обходом в глубину, а всего
таких путей будет
(поскольку каждый путь насыщает как минимум одно edge). Итоговая Asymptotic complexity
поиска одного блокирующего потока составит
.
● Аналогично предыдущей идее, однако удалять в процессе обхода в глубину из đồ thịа все "лишние" рёбра, т.е.
рёбра, вдоль которых не получится дойти до стока. Это очень легко реализовать: достаточно удалять edge после того, как мы просмотрели его в обходе в глубину (кроме того случая, когда мы прошли вдоль ребра и нашли путь до стока). С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое неудалённое edge, и увеличивать этот указать в цикле внутри обхода в глубину. Оценим асимптотику этого решения. Каждый обход в глубину завершается либо насыщением как минимум одного ребра (если этот обход достиг стока), либо продвижением вперёд как минимум одного указателя (в противном случае). Можно понять, что один запуск обхода в глубину из основной программы работает за
, где
—
number продвижений указателей. given, что всего запусков обхода в глубину в рамках поиска одного
блокирующего потока будет
, где
— number рёбер, насыщенных этим блокирующим потоком, то весь
Thuật toán поиска блокирующего потока отработает за
, что, given, что все указатели в сумме
прошли расстояние
, даёт асимптотику
. В худшем случае, когда блокирующий поток насыщает
все рёбра, Asymptotic complexity получается
; эта Asymptotic complexity и будет использоваться далее. Можно сказать, что этот способ нахождения блокирующего потока чрезвычайно эффективен в том смысле, что на
поиск одного увеличивающего пути он тратит
операций в среднем. Именно в этом и кроется разность на
целый порядок эффективностей Thuật toánа Диница и Эдмондса-Карпа (который ищет один увеличивающий путь
за
). Этот способ решения является по-прежнему простым для реализации, но достаточно эффективным, и потому наиболее часто применяется на практике.
● Можно применить специальные структуры данных — динамические деревья Слетора (Sleator) и Тарьяна (Tarjan)).
Тогда каждый блокирующий поток можно find за время
.
Asymptotic complexity
Таким образом, весь Thuật toán Диница выполняется за
, если блокирующий поток искать описанным
выше способом за
. Cài đặt с использованием динамических деревьев Слетора и Тарьяна будет работать
за время
.
Единичные сети
Единичной называется такая сеть, в которой все пропускные способности равны 0 либо 1, и у любой вершины либо Đầu vàoящее, либо исходящее edge единственно. Этот случай является достаточно важным, поскольку в задаче поиска максимального паросочетания построенная сеть является именно единичной. Докажем, что на единичных сетях Thuật toán Диница даже в простой реализации (которая на произвольных
đồ thịах отрабатывает за
) работает за время
, достигая на задаче поиска
наибольшего паросочетания наилучший из известных Thuật toánов — Thuật toán Хопкрофта-Карпа. Чтобы доказать эту оценку, надо рассмотреть два случая:
● Если величина искомого потока не превосходит
. В этом случае мы получаем, что number фаз и запусков обхода в глубину есть величина
. Вспоминая, что
одна фаза в этой реализации работает за
, получаем итоговую
асимптотику
.
● Если величина
искомого потока больше
. Заметим, что поток в единичной сети можно представить в виде суммы
вершинно-непересекающихся путей, а
потому максимальная длина
пути имеет величину
. given, что одна фаза Thuật toánа Диница
целиком обрабатывает все пути какой-либо длины, мы снова получаем, что number фаз есть величина .
Суммируя асимптотику одной фазы
по всем фазам, получаем
, что
и требовалось доказать.
Cài đặt
Приведём две реализации Thuật toánа за
, работающие на сетях, заданных матрицами смежности и
списками смежности соответственно.
Cài đặt над đồ thịами в виде матриц смежности
const int MAXN = ...; // number вершин
const int INF = 1000000000; // константа-бесконечность
int n, c[MAXN][MAXN], f[MAXN][MAXN], s, t, d[MAXN], ptr[MAXN], q[MAXN];bool bfs() {
int qh=0, qt=0;q[qt++] = s;
memset (d, -1, n * sizeof d[0]);
d[s] = 0;
while (qh < qt) {int v = q[qh++];for (int to=0; to<n; ++to)if (d[to] == -1 && f[v][to] < c[v][to]) {q[qt++] = to;
d[to] = d[v] + 1;
} }
return d[t] != -1;}
int dfs (int v, int flow) {if (!flow) return 0;if (v == t) return flow;for (int & to=ptr[v]; to<n; ++to) {if (d[to] != d[v] + 1) continue;int pushed = dfs (to, min (flow, c[v][to] - f[v][to]));if (pushed) {f[v][to] += pushed;
f[to][v] -= pushed;
return pushed;} }
return 0;}
int dinic() {int flow = 0;for (;;) {if (!bfs()) break;memset (ptr, 0, n * sizeof ptr[0]);
while (int pushed = dfs (s, INF))flow += pushed;
}
return flow;} Сеть должна быть предварительно считана: должны быть заgiven переменные
,
,
, а также считана
матрица пропускных способностей
. Основная функция решения —
, которая returns
величину найденного максимального потока.
Cài đặt над đồ thịами в виде списков смежности
const int MAXN = ...; // number вершин
const int INF = 1000000000; // константа-бесконечность
struct edge {
int a, b, cap, flow;};
int n, s, t, d[MAXN], ptr[MAXN], q[MAXN];vector<edge> e;
vector<int> g[MAXN];
void add_edge (int a, int b, int cap) {
edge e1 = { a, b, cap, 0 };
edge e2 = { b, a, 0, 0 };
g[a].push_back ((int) e.size());
e.push_back (e1);
g[b].push_back ((int) e.size());
e.push_back (e2);
}
bool bfs() {
int qh=0, qt=0;q[qt++] = s;
memset (d, -1, n * sizeof d[0]);
d[s] = 0;
while (qh < qt && d[t] == -1) {int v = q[qh++];for (size_t i=0; i<g[v].size(); ++i) {int id = g[v][i],to = e[id].b;
if (d[to] == -1 && e[id].flow < e[id].cap) {q[qt++] = to;
d[to] = d[v] + 1;
} } }
return d[t] != -1;}
int dfs (int v, int flow) {if (!flow) return 0;if (v == t) return flow;for (; ptr[v]<(int)g[v].size(); ++ptr[v]) {int id = g[v][ptr[v]],to = e[id].b;
if (d[to] != d[v] + 1) continue;int pushed = dfs (to, min (flow, e[id].cap - e[id].flow));if (pushed) {e[id].flow += pushed;
e[id^1].flow -= pushed;
return pushed;} }
return 0;}
int dinic() {int flow = 0;for (;;) {if (!bfs()) break;memset (ptr, 0, n * sizeof ptr[0]);
while (int pushed = dfs (s, INF))flow += pushed;
}
return flow;} Сеть должна быть предварительно считана: должны быть заgiven переменные
,
,
, а также добавлены все
рёбра (ориентированные) с помощью вызовов функции
. Основная функция решения —
,
которая returns величину найденного максимального потока.
C# lời giải
bản nháp tự động, xem lại trước khi gửiusing System;
using System.Collections.Generic;
using System.Linq;
public static class AlgorithmDraft
{
// Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
const int MAXN = ...; // число вершин
const int INF = 1000000000; // константа-бесконечность
int n, c[MAXN][MAXN], f[MAXN][MAXN], s, t, d[MAXN], ptr[MAXN], q[MAXN];
bool bfs() {
int qh=0, qt=0;
q[qt++] = s;
memset (d, -1, n * sizeof d[0]);
d[s] = 0;
while (qh < qt) {
int v = q[qh++];
for (int to=0; to<n; ++to)
if (d[to] == -1 && f[v][to] < c[v][to]) {
q[qt++] = to;
d[to] = d[v] + 1;
}
}
return d[t] != -1;
}
int dfs (int v, int flow) {
if (!flow) return 0;
if (v == t) return flow;
for (int & to=ptr[v]; to<n; ++to) {
if (d[to] != d[v] + 1) continue;
int pushed = dfs (to, min (flow, c[v][to] - f[v][to]));
if (pushed) {
f[v][to] += pushed;
f[to][v] -= pushed;
return pushed;
}
}
return 0;
}
int dinic() {
int flow = 0;
for (;;) {
if (!bfs()) break;
memset (ptr, 0, n * sizeof ptr[0]);
while (int pushed = dfs (s, INF))
flow += pushed;
}
return flow;
}
const int MAXN = ...; // число вершин
const int INF = 1000000000; // константа-бесконечность
struct edge {
int a, b, cap, flow;
};
int n, s, t, d[MAXN], ptr[MAXN], q[MAXN];
vector<edge> e;
List<int> g[MAXN];
void add_edge (int a, int b, int cap) {
edge e1 = { a, b, cap, 0 };
edge e2 = { b, a, 0, 0 };
g[a].push_back ((int) e.size());
e.push_back (e1);
g[b].push_back ((int) e.size());
e.push_back (e2);
}
bool bfs() {
int qh=0, qt=0;
q[qt++] = s;
memset (d, -1, n * sizeof d[0]);
d[s] = 0;
while (qh < qt && d[t] == -1) {
int v = q[qh++];
for (size_t i=0; i<g[v].size(); ++i) {
int id = g[v][i],
to = e[id].b;
if (d[to] == -1 && e[id].flow < e[id].cap) {
q[qt++] = to;
d[to] = d[v] + 1;
}
}
}
return d[t] != -1;
}
int dfs (int v, int flow) {
if (!flow) return 0;
if (v == t) return flow;
for (; ptr[v]<(int)g[v].size(); ++ptr[v]) {
int id = g[v][ptr[v]],
to = e[id].b;
if (d[to] != d[v] + 1) continue;
int pushed = dfs (to, min (flow, e[id].cap - e[id].flow));
if (pushed) {
e[id].flow += pushed;
e[id^1].flow -= pushed;
return pushed;
}
}
return 0;
}
int dinic() {
int flow = 0;
for (;;) {
if (!bfs()) break;
memset (ptr, 0, n * sizeof ptr[0]);
while (int pushed = dfs (s, INF))
flow += pushed;
}
return flow;
}
}C++ lời giải
đã khớp/gốcconst int MAXN = ...; // число вершин
const int INF = 1000000000; // константа-бесконечность
int n, c[MAXN][MAXN], f[MAXN][MAXN], s, t, d[MAXN], ptr[MAXN], q[MAXN];
bool bfs() {
int qh=0, qt=0;
q[qt++] = s;
memset (d, -1, n * sizeof d[0]);
d[s] = 0;
while (qh < qt) {
int v = q[qh++];
for (int to=0; to<n; ++to)
if (d[to] == -1 && f[v][to] < c[v][to]) {
q[qt++] = to;
d[to] = d[v] + 1;
}
}
return d[t] != -1;
}
int dfs (int v, int flow) {
if (!flow) return 0;
if (v == t) return flow;
for (int & to=ptr[v]; to<n; ++to) {
if (d[to] != d[v] + 1) continue;
int pushed = dfs (to, min (flow, c[v][to] - f[v][to]));
if (pushed) {
f[v][to] += pushed;
f[to][v] -= pushed;
return pushed;
}
}
return 0;
}
int dinic() {
int flow = 0;
for (;;) {
if (!bfs()) break;
memset (ptr, 0, n * sizeof ptr[0]);
while (int pushed = dfs (s, INF))
flow += pushed;
}
return flow;
}
const int MAXN = ...; // число вершин
const int INF = 1000000000; // константа-бесконечность
struct edge {
int a, b, cap, flow;
};
int n, s, t, d[MAXN], ptr[MAXN], q[MAXN];
vector<edge> e;
vector<int> g[MAXN];
void add_edge (int a, int b, int cap) {
edge e1 = { a, b, cap, 0 };
edge e2 = { b, a, 0, 0 };
g[a].push_back ((int) e.size());
e.push_back (e1);
g[b].push_back ((int) e.size());
e.push_back (e2);
}
bool bfs() {
int qh=0, qt=0;
q[qt++] = s;
memset (d, -1, n * sizeof d[0]);
d[s] = 0;
while (qh < qt && d[t] == -1) {
int v = q[qh++];
for (size_t i=0; i<g[v].size(); ++i) {
int id = g[v][i],
to = e[id].b;
if (d[to] == -1 && e[id].flow < e[id].cap) {
q[qt++] = to;
d[to] = d[v] + 1;
}
}
}
return d[t] != -1;
}
int dfs (int v, int flow) {
if (!flow) return 0;
if (v == t) return flow;
for (; ptr[v]<(int)g[v].size(); ++ptr[v]) {
int id = g[v][ptr[v]],
to = e[id].b;
if (d[to] != d[v] + 1) continue;
int pushed = dfs (to, min (flow, e[id].cap - e[id].flow));
if (pushed) {
e[id].flow += pushed;
e[id^1].flow -= pushed;
return pushed;
}
}
return 0;
}
int dinic() {
int flow = 0;
for (;;) {
if (!bfs()) break;
memset (ptr, 0, n * sizeof ptr[0]);
while (int pushed = dfs (s, INF))
flow += pushed;
}
return flow;
}Java lời giải
bản nháp tự động, xem lại trước khi gửiimport java.util.*;
import java.math.*;
public class AlgorithmDraft {
// Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
const int MAXN = ...; // число вершин
const int INF = 1000000000; // константа-бесконечность
int n, c[MAXN][MAXN], f[MAXN][MAXN], s, t, d[MAXN], ptr[MAXN], q[MAXN];
boolean bfs() {
int qh=0, qt=0;
q[qt++] = s;
memset (d, -1, n * sizeof d[0]);
d[s] = 0;
while (qh < qt) {
int v = q[qh++];
for (int to=0; to<n; ++to)
if (d[to] == -1 && f[v][to] < c[v][to]) {
q[qt++] = to;
d[to] = d[v] + 1;
}
}
return d[t] != -1;
}
int dfs (int v, int flow) {
if (!flow) return 0;
if (v == t) return flow;
for (int & to=ptr[v]; to<n; ++to) {
if (d[to] != d[v] + 1) continue;
int pushed = dfs (to, min (flow, c[v][to] - f[v][to]));
if (pushed) {
f[v][to] += pushed;
f[to][v] -= pushed;
return pushed;
}
}
return 0;
}
int dinic() {
int flow = 0;
for (;;) {
if (!bfs()) break;
memset (ptr, 0, n * sizeof ptr[0]);
while (int pushed = dfs (s, INF))
flow += pushed;
}
return flow;
}
const int MAXN = ...; // число вершин
const int INF = 1000000000; // константа-бесконечность
struct edge {
int a, b, cap, flow;
};
int n, s, t, d[MAXN], ptr[MAXN], q[MAXN];
vector<edge> e;
ArrayList<Integer> g[MAXN];
void add_edge (int a, int b, int cap) {
edge e1 = { a, b, cap, 0 };
edge e2 = { b, a, 0, 0 };
g[a].push_back ((int) e.size());
e.push_back (e1);
g[b].push_back ((int) e.size());
e.push_back (e2);
}
boolean bfs() {
int qh=0, qt=0;
q[qt++] = s;
memset (d, -1, n * sizeof d[0]);
d[s] = 0;
while (qh < qt && d[t] == -1) {
int v = q[qh++];
for (size_t i=0; i<g[v].size(); ++i) {
int id = g[v][i],
to = e[id].b;
if (d[to] == -1 && e[id].flow < e[id].cap) {
q[qt++] = to;
d[to] = d[v] + 1;
}
}
}
return d[t] != -1;
}
int dfs (int v, int flow) {
if (!flow) return 0;
if (v == t) return flow;
for (; ptr[v]<(int)g[v].size(); ++ptr[v]) {
int id = g[v][ptr[v]],
to = e[id].b;
if (d[to] != d[v] + 1) continue;
int pushed = dfs (to, min (flow, e[id].cap - e[id].flow));
if (pushed) {
e[id].flow += pushed;
e[id^1].flow -= pushed;
return pushed;
}
}
return 0;
}
int dinic() {
int flow = 0;
for (;;) {
if (!bfs()) break;
memset (ptr, 0, n * sizeof ptr[0]);
while (int pushed = dfs (s, INF))
flow += pushed;
}
return flow;
}
}Материал разбит как Thuật toánическая Bài toán: изучить постановку, понять асимптотику и реализовать Thuật toán на выбранном языке.
Vacancies for this task
việc làm đang hoạt động with overlapping task tags are đã hiển thị.