MAXimal | |
добавлено: 10 Jun 2008 22:53 Содержание [скрыть] Модификация метода Проталкивания предпотока для нахождения максимального потока за O (N3)Предполагается, что вы уже прочитали Метод Проталкивания предпотока нахождения максимального потока за 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 ... }
|