Максимальный поток методом Проталкивания предпотока за O (N⁴)

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

Задача заключается в нахождении максимального потока. Здесь будет рассмотрен метод Проталкивания предпотока, работающий за O (N⁴), или, точнее, за O (N² M). Алгоритм был предложен Гольдбергом в 1985 году.

Алгоритм

Общая схема алгоритма такова. На каждом шаге будем рассматривать некоторый предпоток - т.е. функцию, которая по свойствам напоминает поток, но не обязательно удовлетворяет закону сохранения потока. На каждом шаге будем пытаться применить какую-либо из двух операций: проталкивание потока или поднятие вершины. Если на каком-то шаге станет невозможно применить какую-либо из двух операций, то мы нашли требуемый поток.

Для каждой вершины определена её высота H_u, причём H_S = N, H_T = 0, и для любого остаточного ребра (u, v) имеем H_u <= H_v + 1.

Для каждой вершины (кроме S) можно определить её избыток: E_u = F_{V, u}. Вершина с положительным избытком называется переполненной.

Операция проталкивания Push (u, v) применима, если вершина u переполнена, остаточная пропускная способность Cf_{u, v} > 0 и H_u = H_v + 1. Операция проталкивания заключается в максимальном увеличении потока из u в v, ограниченном избытком E_u и остаточной пропускной способностью Cf_{u, v}.

Операция поднятия Lift (u) поднимает переполненную вершину u на максимально допустимую высоту. Т.е. H_u = 1 + min { H_v }, где (u, v) - остаточное ребро.

Осталось только рассмотреть инициализацию потока. Нужно инициализировать только следующие значения: F_{S, v} = C_{S, v}, F_{u, S} = - C_{u, S}, остальные значения положить равными нулю.

Реализация

const int inf = 1000*1000*1000;


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

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


void push (int u, int v, vvint & f, vint & e, const vvint & c)
{
	int d = min (e[u], c[u][v] - f[u][v]);
	f[u][v] += d;
	f[v][u] = - f[u][v];
	e[u] -= d;
	e[v] += d;
}

void lift (int u, vint & h, const vvint & f, const vvint & c)
{
	int d = inf;
	for (int i = 0; i < (int)f.size(); i++)
		if (c[u][i]-f[u][i] > 0)
			d = min (d, h[i]);
	if (d == inf)
		return;
	h[u] = d + 1;
}


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 (int i=1; i<n; i++)
	{
		f[0][i] = c[0][i];
		f[i][0] = -c[0][i];
	}

	vint h (n);
	h[0] = n;

	vint e (n);
	for (int i=1; i<n; i++)
		e[i] = f[0][i];

	for ( ; ; )
	{
		int i;
		for (i=1; i<n-1; i++)
			if (e[i] > 0)
				break;
		if (i == n-1)
			break;

		int j;
		for (j=0; j<n; j++)
			if (c[i][j]-f[i][j] > 0 && h[i]==h[j]+1)
				break;
		if (j < n)
			push (i, j, f, e, c);
		else
			lift (i, h, f, c);
	}

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

	cout << max(flow,0);

}

Максимальный поток методом Проталкивания предпотока за O (N4)

Алгоритм

Реализация

Максимальный поток методом Проталкивания предпотока за O (N⁴)