С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

Максимальный поток в графе, объясните идиоту - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Сравнить значения выдаваемые 2-мя функциями http://www.cyberforum.ru/cpp-beginners/thread297361.html
Всем привет! написал программу игра в кости... есть две функции draw1,draw2 которые рисуют кости для 1 и 2 игрока и подсчитывают число выпавших костей отдельно для каждого игрока. Как сделать так...
C++ Написать программу заполнения массива A[1..N,1..M] нулями и единицами в шахматном порядке кому по силам сделать какие задачи??надо в pelles c! Задание 1. Написать программу заполнения массива A нулями и единицами в шахматном порядке. Задание 2. Заменить все гласные в слове на их... http://www.cyberforum.ru/cpp-beginners/thread297357.html
Очередь на основе массива C++
Сделал программу, которая создает очередь с помощью массива. Но работает она криво.Например, если ввести длину очереди 3 элемента, написать их, а затем удалить 2 из них, то все будет нормально, но...
Решить квадратное уравнение a*x^2+b*x+c=0 C++
Даны три массива A,B,C: Решить квадратное уравнение a*x^2+b*x+c=0 ,где a,b,c-сумма квадратов элементов меньших чем сумма всех элементов в массивах A,B,C соответственно.
C++ Найти сумму элементов в тех столбцах,которые содержат хотя бы один отрицательный элемент http://www.cyberforum.ru/cpp-beginners/thread297330.html
Характеристикой столбца целочисленной матрицы назовём сумму модулей его отрицательных нечётных элементов.Переставляя столбцы заданной матрицы,расположить их в соответствии с ростом характеристик. ...
C++ написание выражения как записать выражение (Ац МОД2 Вц) и НЕ(Ац или Сц)? Через Ац,Вц,Сц обозначены целые части значения a,b,c, операции И,ИЛИ,МОД(сложение по модулю 2)-поразрядные. подробнее

Показать сообщение отдельно
nikola166
8 / 8 / 0
Регистрация: 18.03.2010
Сообщений: 142

Максимальный поток в графе, объясните идиоту - C++

16.05.2011, 23:18. Просмотров 4527. Ответов 10
Метки (Все метки)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
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;
 
}
есть код, это алгоритм Эдмондса-Карпа, не пойму каким образом здесь задается граф и сток и исток, т.е вершины от которой до которой ищем максимальный поток, вроде тут матрицей задается, но что-то она какая то странная, не понятно какой граф задается, ореентированный или нет, помогите пожалуйста разобраться.
Заранее спасибо товарищи программеры)

 Комментарий модератора 
Используйте теги форматирования кода!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.