E051. maximum поток методом Эдмондса-Карпа за O (N M2)

e-maxx algorithm original: C/C++ #algorithm #emaxx #flow #graph #hashing

题目文本会按所选界面语言从俄语翻译；代码保持不变。

Static

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

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

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

算法

Остаточной пропускной способностью называется пропускная способность ребра за вычетом текущего потока вдоль этого ребра. При этом надо помнить, что если некоторый поток протекает по ориентированному ребру, то возникает так называемое обратное edge (направленное в обратную сторону), которое будет иметь нулевую пропускную способность, и по которому будет протекать тот же по величине поток, но со знаком минус. Если же edge было неориентированным, то оно как бы распадается на два ориентированных ребра с одинаковой пропускной способностью, и каждое из этих рёбер является обратным для другого (если по одному протекает поток F, то по другому протекает -F). Общая схема 算法а Эдмондса-Карпа такова. Сначала полагаем поток равным нулю. Затем ищем дополняющий путь, т.е. простой путь из S в T по тем рёбрам, у которых остаточная пропускная способность строго положительна. Если дополняющий путь был найден, то производится увеличение текущего потока вдоль этого пути. Если же пути не было найдено, то текущий поток является максимальным. Для поиска дополняющего пути может использоваться как Обход в ширину, так и Обход в глубину. Рассмотрим более точно процедуру увеличения потока. Пусть мы нашли некоторый дополняющий путь, тогда пусть C - наименьшая из остаточных пропускных способностей рёбер этого пути. Процедура увеличения потока заключается в следующем: для каждого ребра (u, v) дополняющего пути выполним: Fu, v += C, а Fv, u = - Fu, v (или, что то же самое, Fv, u -= C). Величиной потока будет сумма всех неотрицательных величин FS, v, где v - любая vertex, соединённая с истоком.

实现

const int inf = 100010001000;

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];

// исток - vertex 0, сток - vertex 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# 解法

自动草稿，提交前请检查

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++ 解法

匹配/原始

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 解法

自动草稿，提交前请检查

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;
    }
}

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

Vacancies for this task

活跃职位 with overlapping task tags are 已显示.

所有职位

目前还没有活跃职位。