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