E053. Модификация метода Проталкивания предпотока для нахождения максимального потока за O (N3)
Источник: e-maxx.ru/algo, страница PDF 153.
Предполагается, что вы уже прочитали Метод Проталкивания предпотока нахождения максимального потока за O (N4).
Описание
Модификация чрезвычайно проста: на каждой итерации среди всех переполненных вершин мы выбираем только те вершины, которые имеют набольшую высоту, и применяем проталкивание/поднятие только к этим вершинам. Более того, для выбора вершин с наибольшей высотой нам не понадобятся никакие структуры данных, достаточно просто хранить список вершин с наибольшей высотой и просто пересчитывать его, если все вершины из этого списка были обработаны (тогда в список добавятся вершины с уже меньшей высотой), а при появлении новой переполненной вершины с большей высотой, чем в списке, очищать список и добавлять вершину в список. Несмотря на простоту, эта модификация позволяет снизить асимптотику на целый порядок. Если быть точным, асимптотика получившего алгоритма равна O (N M + N2 sqrt (M)), что в худшем случае составляет O (N3). Эта модификация была предложена Черияном (Cheriyan) и Махешвари (Maheshvari) в 1989 г.
Реализация
Здесь приведена готовая реализация этого алгоритма. Отличие от обычного алгоритма проталкивания - только в наличии массива maxh, в котором будут храниться номера переполненных вершин с максимальной высотой. Размер массива указан в переменной sz. Если на какой- то итерации оказывается, что этот массив пустой (sz==0), то мы заполняем его (просто проходя по всем вершинам); если после этого массив по-прежнему пустой, то переполненных вершин нет, и алгоритм останавливается. Иначе мы проходим по вершинам в этом списке, применяя к ним проталкивание или поднятие. После выполнения операции проталкивания текущая вершина может перестать быть переполненной, в этом случае удаляем её из списка maxh. Если после какой-то операции поднятия высота текущей вершины становится больше высоты вершин в списке maxh, то мы очищаем список (sz=0), и сразу переходим к следующей итерации алгоритма проталкивания (на которой будет построен новый список maxh).
const int INF = 1000*1000*1000;
int main() {int n;vector < vector<int> > c (n, vector<int> (n));
int s, t;... чтение n, c, s, t ...
vector<int> e (n);
vector<int> h (n);
h[s] = n-1;
vector < vector<int> > f (n, vector<int> (n));
for (int i=0; i<n; ++i) {f[s][i] = c[s][i];
f[i][s] = -f[s][i];
e[i] = c[s][i];
}
vector<int> maxh (n);
int sz = 0;for (;;) {if (!sz)for (int i=0; i<n; ++i)if (i != s && i != t && e[i] > 0) {if (sz && h[i] > h[maxh[0]])sz = 0;
if (!sz || h[i] == h[maxh[0]])maxh[sz++] = i;
}
if (!sz) break;while (sz) {int i = maxh[sz-1];bool pushed = false;
for (int j=0; j<n && e[i]; ++j)if (c[i][j]-f[i][j] > 0 && h[i] == h[j]+1) {pushed = true;
int addf = min (c[i][j]-f[i][j], e[i]);f[i][j] += addf, f[j][i] -= addf;
e[i] -= addf, e[j] += addf;
if (e[i] == 0) --sz;}
if (!pushed) {h[i] = INF;
for (int j=0; j<n; ++j)if (c[i][j]-f[i][j] > 0 && h[j]+1 <h[i])
h[i] = h[j]+1;
if (h[i] > h[maxh[0]]) {sz = 0;
break;
} } } } ... вывод потока f ... }
C# решение
auto-draft, проверить перед отправкойusing 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 INF = 1000*1000*1000;
int main() {
int n;
vector < List<int> > c (n, List<int> (n));
int s, t;
... чтение n, c, s, t ...
List<int> e (n);
List<int> h (n);
h[s] = n-1;
vector < List<int> > f (n, List<int> (n));
for (int i=0; i<n; ++i) {
f[s][i] = c[s][i];
f[i][s] = -f[s][i];
e[i] = c[s][i];
}
List<int> maxh (n);
int sz = 0;
for (;;) {
if (!sz)
for (int i=0; i<n; ++i)
if (i != s && i != t && e[i] > 0) {
if (sz && h[i] > h[maxh[0]])
sz = 0;
if (!sz || h[i] == h[maxh[0]])
maxh[sz++] = i;
}
if (!sz) break;
while (sz) {
int i = maxh[sz-1];
bool pushed = false;
for (int j=0; j<n && e[i]; ++j)
if (c[i][j]-f[i][j] > 0 && h[i] == h[j]+1) {
pushed = true;
int addf = min (c[i][j]-f[i][j], e[i]);
f[i][j] += addf, f[j][i] -= addf;
e[i] -= addf, e[j] += addf;
if (e[i] == 0) --sz;
}
if (!pushed) {
h[i] = INF;
for (int j=0; j<n; ++j)
if (c[i][j]-f[i][j] > 0 && h[j]+1 <
h[i])
h[i] = h[j]+1;
if (h[i] > h[maxh[0]]) {
sz = 0;
break;
}
}
}
}
... вывод потока f ...
}
}C++ решение
сопоставлено/оригиналconst int INF = 1000*1000*1000;
int main() {
int n;
vector < vector<int> > c (n, vector<int> (n));
int s, t;
... чтение n, c, s, t ...
vector<int> e (n);
vector<int> h (n);
h[s] = n-1;
vector < vector<int> > f (n, vector<int> (n));
for (int i=0; i<n; ++i) {
f[s][i] = c[s][i];
f[i][s] = -f[s][i];
e[i] = c[s][i];
}
vector<int> maxh (n);
int sz = 0;
for (;;) {
if (!sz)
for (int i=0; i<n; ++i)
if (i != s && i != t && e[i] > 0) {
if (sz && h[i] > h[maxh[0]])
sz = 0;
if (!sz || h[i] == h[maxh[0]])
maxh[sz++] = i;
}
if (!sz) break;
while (sz) {
int i = maxh[sz-1];
bool pushed = false;
for (int j=0; j<n && e[i]; ++j)
if (c[i][j]-f[i][j] > 0 && h[i] == h[j]+1) {
pushed = true;
int addf = min (c[i][j]-f[i][j], e[i]);
f[i][j] += addf, f[j][i] -= addf;
e[i] -= addf, e[j] += addf;
if (e[i] == 0) --sz;
}
if (!pushed) {
h[i] = INF;
for (int j=0; j<n; ++j)
if (c[i][j]-f[i][j] > 0 && h[j]+1 <
h[i])
h[i] = h[j]+1;
if (h[i] > h[maxh[0]]) {
sz = 0;
break;
}
}
}
}
... вывод потока f ...
}Java решение
auto-draft, проверить перед отправкойimport 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 INF = 1000*1000*1000;
int main() {
int n;
vector < ArrayList<Integer> > c (n, ArrayList<Integer> (n));
int s, t;
... чтение n, c, s, t ...
ArrayList<Integer> e (n);
ArrayList<Integer> h (n);
h[s] = n-1;
vector < ArrayList<Integer> > f (n, ArrayList<Integer> (n));
for (int i=0; i<n; ++i) {
f[s][i] = c[s][i];
f[i][s] = -f[s][i];
e[i] = c[s][i];
}
ArrayList<Integer> maxh (n);
int sz = 0;
for (;;) {
if (!sz)
for (int i=0; i<n; ++i)
if (i != s && i != t && e[i] > 0) {
if (sz && h[i] > h[maxh[0]])
sz = 0;
if (!sz || h[i] == h[maxh[0]])
maxh[sz++] = i;
}
if (!sz) break;
while (sz) {
int i = maxh[sz-1];
boolean pushed = false;
for (int j=0; j<n && e[i]; ++j)
if (c[i][j]-f[i][j] > 0 && h[i] == h[j]+1) {
pushed = true;
int addf = min (c[i][j]-f[i][j], e[i]);
f[i][j] += addf, f[j][i] -= addf;
e[i] -= addf, e[j] += addf;
if (e[i] == 0) --sz;
}
if (!pushed) {
h[i] = INF;
for (int j=0; j<n; ++j)
if (c[i][j]-f[i][j] > 0 && h[j]+1 <
h[i])
h[i] = h[j]+1;
if (h[i] > h[maxh[0]]) {
sz = 0;
break;
}
}
}
}
... вывод потока f ...
}
}Материал разбит как алгоритмическая задача: изучить постановку, понять асимптотику и реализовать алгоритм на выбранном языке.
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.