E052. Максимальный поток методом Проталкивания предпотока за O (N4)
Источник: e-maxx.ru/algo, страница PDF 151.
Пусть дан граф G, в котором выделены две вершины: исток S и сток T, а у каждого ребра определена пропускная способность Cu,v. Поток F можно представить как поток вещества, которое могло бы пройти по сети от истока к стоку, если рассматривать граф как сеть труб с некоторыми пропускными способностями. Т.е. поток - функция Fu, v, определённая на множестве рёбер графа.
Задача заключается в нахождении максимального потока. Здесь будет рассмотрен метод Проталкивания предпотока, работающий за O (N4), или, точнее, за O (N2 M). Алгоритм был предложен Гольдбергом в 1985 году.
Алгоритм
Общая схема алгоритма такова. На каждом шаге будем рассматривать некоторый предпоток - т.е. функцию, которая по свойствам напоминает поток, но не обязательно удовлетворяет закону сохранения потока. На каждом шаге будем пытаться применить какую-либо из двух операций: проталкивание потока или поднятие вершины. Если на каком- то шаге станет невозможно применить какую-либо из двух операций, то мы нашли требуемый поток. Для каждой вершины определена её высота Hu, причём HS = N, HT = 0, и для любого остаточного ребра (u, v) имеем Hu <= Hv + 1. Для каждой вершины (кроме S) можно определить её избыток: Eu = FV, u. Вершина с положительным избытком называется переполненной. Операция проталкивания Push (u, v) применима, если вершина u переполнена, остаточная пропускная способность Cfu, v > 0 и Hu = Hv + 1. Операция проталкивания заключается в максимальном увеличении потока из u в v, ограниченном избытком Eu и остаточной пропускной способностью Cfu, v. Операция поднятия Lift (u) поднимает переполненную вершину u на максимально допустимую высоту. Т.е. Hu = 1 + min { Hv }, где (u, v) - остаточное ребро. Осталось только рассмотреть инициализацию потока. Нужно инициализировать только следующие значения: FS, v = CS, v, Fu, S = - Cu, 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);
}
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;
typedef List<int> graf_line;
typedef vector<graf_line> graf;
typedef List<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];
Console.WriteLine( max(flow,0);
}
}C++ решение
сопоставлено/оригинал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);
}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;
typedef ArrayList<Integer> graf_line;
typedef vector<graf_line> graf;
typedef ArrayList<Integer> 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];
System.out.println( max(flow,0);
}
}Материал разбит как алгоритмическая задача: изучить постановку, понять асимптотику и реализовать алгоритм на выбранном языке.
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.