MAXimal

добавлено: 10 Jun 2008 22:50
редактировано: 2 May 2012 0:47

Максимальный поток методом Эдмондса-Карпа за O (N M2)

Внимание: данная статья устарела и содержит ошибки и не рекомендуется к чтению. Через некоторое время статья будет полностью переписана.

Пусть дан граф G, в котором выделены две вершины: исток S и сток T, а у каждого ребра определена пропускная способность Cu,v. Поток F можно представить как поток вещества, которое могло бы пройти по сети от истока к стоку, если рассматривать граф как сеть труб с некоторыми пропускными способностями. Т.е. поток - функция Fu, v, определённая на множестве рёбер графа.

 

Задача заключается в нахождении максимального потока. Здесь будет рассмотрен метод Эдмондса-Карпа, работающий за O (N M2), или (другая оценка) O (F M), где F - величина искомого потока. Алгоритм был предложен в 1972 году.

Алгоритм

Остаточной пропускной способностью называется пропускная способность ребра за вычетом текущего потока вдоль этого ребра. При этом надо помнить, что если некоторый поток протекает по ориентированному ребру, то возникает так называемое обратное ребро (направленное в обратную сторону), которое будет иметь нулевую пропускную способность, и по которому будет протекать тот же по величине поток, но со знаком минус. Если же ребро было неориентированным, то оно как бы распадается на два ориентированных ребра с одинаковой пропускной способностью, и каждое из этих рёбер является обратным для другого (если по одному протекает поток F, то по другому протекает -F).

Общая схема алгоритма Эдмондса-Карпа такова. Сначала полагаем поток равным нулю. Затем ищем дополняющий путь, т.е. простой путь из S в T по тем рёбрам, у которых остаточная пропускная способность строго положительна. Если дополняющий путь был найден, то производится увеличение текущего потока вдоль этого пути. Если же пути не было найдено, то текущий поток является максимальным. Для поиска дополняющего пути может использоваться как Обход в ширину, так и Обход в глубину.

Рассмотрим более точно процедуру увеличения потока. Пусть мы нашли некоторый дополняющий путь, тогда пусть C - наименьшая из остаточных пропускных способностей рёбер этого пути. Процедура увеличения потока заключается в следующем: для каждого ребра (u, v) дополняющего пути выполним: Fu, v += C, а Fv, u = - Fu, v (или, что то же самое, Fv, u -= C).

Величиной потока будет сумма всех неотрицательных величин FS, v, где v - любая вершина, соединённая с истоком.

Реализация

const int inf = 1000*1000*1000;


typedef vector<int> graf_line;
typedef vector<graf_line> graf;

typedef vector<int> vint;
typedef vector<vint> vvint;


int main()
{
	int n;
	cin >> n;
	vvint c (n, vint(n));
	for (int i=0; i<n; i++)
		for (int j=0; j<n; j++)
			cin >> c[i][j];
	// исток - вершина 0, сток - вершина n-1

	vvint f (n, vint(n));
	for (;;)
	{
		
		vint from (n, -1);
		vint q (n);
		int h=0, t=0;
		q[t++] = 0;
		from[0] = 0;
		for (int cur; h<t;)
		{
			cur = q[h++];
			for (int v=0; v<n; v++)
				if (from[v] == -1 &&
					c[cur][v]-f[cur][v] > 0)
				{
					q[t++] = v;
					from[v] = cur;
				}
		}

		if (from[n-1] == -1)
			break;
		int cf = inf;
		for (int cur=n-1; cur!=0; )
		{
			int prev = from[cur];
			cf = min (cf, c[prev][cur]-f[prev][cur]);
			cur = prev;
		}

		for (int cur=n-1; cur!=0; )
		{
			int prev = from[cur];
			f[prev][cur] += cf;
			f[cur][prev] -= cf;
			cur = prev;
		}

	}

	int flow = 0;
	for (int i=0; i<n; i++)
		if (c[0][i])
			flow += f[0][i];

	cout << flow;

}