MAXimal

добавлено: 10 Jun 2008 22:53
редактировано: 14 Oct 2011 0:31

Модификация метода Проталкивания предпотока для нахождения максимального потока за 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 ...

}