Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 32, средняя оценка - 4.66
nikola166
 Аватар для nikola166
8 / 8 / 0
Регистрация: 18.03.2010
Сообщений: 142
16.05.2011, 23:18     Максимальный поток в графе, объясните идиоту #1
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;
 
}
есть код, это алгоритм Эдмондса-Карпа, не пойму каким образом здесь задается граф и сток и исток, т.е вершины от которой до которой ищем максимальный поток, вроде тут матрицей задается, но что-то она какая то странная, не понятно какой граф задается, ореентированный или нет, помогите пожалуйста разобраться.
Заранее спасибо товарищи программеры)

 Комментарий модератора 
Используйте теги форматирования кода!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.05.2011, 23:18     Максимальный поток в графе, объясните идиоту
Посмотрите здесь:

Нужно создать базу данных (создать пустой бинарный файл). Через поток. Поток бинарного файла описать в виде локальной переменной внутри функции. C++
Максимальный элемени матрицы заменить на нуль и вывести на печать угол матрицы, в котором расположен этот максимальный элемент C++
Скопировать поток и добавить ошибки в поток C++
C++ Скопировать поток в поток
C++ Заменить максимальный элемент в матрице, средним арифметическим элементов строки, в которой находится максимальный элемент
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
-comrade-
355 / 356 / 42
Регистрация: 11.06.2010
Сообщений: 703
16.05.2011, 23:23     Максимальный поток в графе, объясните идиоту #2
nikola166, максимальный поток в графе нельзя найти, его ищут на транспортной сети.
Алгоритм Эдмондса-Карпа.
nikola166
 Аватар для nikola166
8 / 8 / 0
Регистрация: 18.03.2010
Сообщений: 142
16.05.2011, 23:51  [ТС]     Максимальный поток в графе, объясните идиоту #3
А транспортная сеть это не граф????? помогите разобраться как тут транспортная сеть задается

Добавлено через 1 минуту
и каким образом здесь задается граф и сток и исток, т.е вершины от которой до которой ищем максимальный поток, вроде тут матрицей задается, но что-то она какая то странная
-comrade-
355 / 356 / 42
Регистрация: 11.06.2010
Сообщений: 703
16.05.2011, 23:57     Максимальный поток в графе, объясните идиоту #4
nikola166, транспортная сеть — ориентированный граф http://www.cyberforum.ru/cgi-bin/latex.cgi?G=(V,E), в котором каждое ребро http://www.cyberforum.ru/cgi-bin/latex.cgi?(u,v) \subset  E имеет неотрицательную пропускную способность http://www.cyberforum.ru/cgi-bin/latex.cgi?c(u,v)\geq 0 и поток http://www.cyberforum.ru/cgi-bin/latex.cgi?f(u,v).

Добавлено через 1 минуту
Читайте здесь и здесь.
nikola166
 Аватар для nikola166
8 / 8 / 0
Регистрация: 18.03.2010
Сообщений: 142
17.05.2011, 00:00  [ТС]     Максимальный поток в графе, объясните идиоту #5
что ты мне википедию суешь, я пользоваться поиском умею, я спросил что меня конкретно интересует, а ты мне ересь кидаешь, которой я уже начитался
-comrade-
355 / 356 / 42
Регистрация: 11.06.2010
Сообщений: 703
17.05.2011, 00:02     Максимальный поток в графе, объясните идиоту #6
Цитата Сообщение от nikola166 Посмотреть сообщение
и каким образом здесь задается граф и сток и исток, т.е вершины от которой до которой ищем максимальный поток, вроде тут матрицей задается, но что-то она какая то странная
Это вы должны знать, ваш же код

Добавлено через 1 минуту
Цитата Сообщение от nikola166 Посмотреть сообщение
что ты мне википедию суешь, я пользоваться поиском умею, я спросил что меня конкретно интересует, а ты мне ересь кидаешь, которой я уже начитался
Значит плохо читали, там четко написано что такое транспортная сетка.
nikola166
 Аватар для nikola166
8 / 8 / 0
Регистрация: 18.03.2010
Сообщений: 142
17.05.2011, 00:04  [ТС]     Максимальный поток в графе, объясните идиоту #7
Это алгоритм я взял с сайта алгоритмов, если бы я сам это писал я бы не спрашивал
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
17.05.2011, 07:10     Максимальный поток в графе, объясните идиоту #8
Цитата Сообщение от nikola166 Посмотреть сообщение
не пойму каким образом здесь задается граф и сток и исток, т.е вершины от которой до которой ищем максимальный поток, вроде тут матрицей задается, но что-то она какая то странная, не понятно какой граф задается, ореентированный или нет
Сначало пользователь вводит кол-во вершин
Цитата Сообщение от nikola166 Посмотреть сообщение
cin >> n;
Затем вводятся данные о графе, а именно о пропускной способности каждого ребра.
Цитата Сообщение от nikola166 Посмотреть сообщение
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
cin >> c[i][j];
Если ребро от вершины i до вершины j имеет пропускную способность X, то для c[i][j] вводим значение X. Если связи между вершинами нет, то для c[i][j] вводим 0. (Замечу, что c[i][j] не обязательно равно c[j][i]).
Сток и исток не задаются. Для данного кода они подразумеваются:
Цитата Сообщение от nikola166 Посмотреть сообщение
// исток - вершина 0, сток - вершина n-1
nikola166
 Аватар для nikola166
8 / 8 / 0
Регистрация: 18.03.2010
Сообщений: 142
17.05.2011, 22:21  [ТС]     Максимальный поток в графе, объясните идиоту #9
а почему здесь задается еще связь вершины с самой собой
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.05.2011, 05:13     Максимальный поток в графе, объясните идиоту #10
Цитата Сообщение от nikola166 Посмотреть сообщение
а почему здесь задается еще связь вершины с самой собой
Бывают графы и с петлями. Вы можете задавать вес петле любой (0 или отличный от 0), но на результат это не отразится.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.05.2011, 22:57     Максимальный поток в графе, объясните идиоту
Еще ссылки по теме:

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

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
nikola166
 Аватар для nikola166
8 / 8 / 0
Регистрация: 18.03.2010
Сообщений: 142
18.05.2011, 22:57  [ТС]     Максимальный поток в графе, объясните идиоту #11
спасибо за помощь))))))
Yandex
Объявления
18.05.2011, 22:57     Максимальный поток в графе, объясните идиоту
Ответ Создать тему
Опции темы

Текущее время: 07:17. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru