← Static tasks

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

emaxx algorithm

#algorithm#emaxx#flow#graph#hashing

Task

Источник: e-maxx.ru/algo, страница PDF 149.

Пусть дан граф 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;

}

C# solution

auto-draft, review before submit
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;
    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];
            Console.WriteLine( flow;
    }
}

C++ solution

matched/original
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;
}

Java solution

auto-draft, review before submit
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;
    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];
            System.out.println( flow;
    }
}

Explanation

Материал разбит как алгоритмическая задача: изучить постановку, понять асимптотику и реализовать алгоритм на выбранном языке.