Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.89/37: Рейтинг темы: голосов - 37, средняя оценка - 4.89
 Аватар для nikola166
10 / 10 / 1
Регистрация: 18.03.2010
Сообщений: 142

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

16.05.2011, 23:18. Показов 7812. Ответов 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
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
16.05.2011, 23:18
Ответы с готовыми решениями:

Максимальный поток в графе
доброе время суток, нужно найти максимальный поток с помощью алгоритма Форда-Фалкерсона

Максимальный поток в неориентированном графе
Какой алгоритм следует использовать для нахождения максимального потока в неориентированном графе(существуют ли они или следует...

Объясните идиоту... MAK и KSM ключи от win 7 enterprise, смогу активировать дома?
Не судите строго... На ебее человек продавал виндоус 7 корпоративный (enterprise), продавец солидный по отзывам ну я и рискнул взять за...

10
365 / 366 / 167
Регистрация: 11.06.2010
Сообщений: 703
16.05.2011, 23:23
nikola166, максимальный поток в графе нельзя найти, его ищут на транспортной сети.
Алгоритм Эдмондса-Карпа.
0
 Аватар для nikola166
10 / 10 / 1
Регистрация: 18.03.2010
Сообщений: 142
16.05.2011, 23:51  [ТС]
А транспортная сеть это не граф????? помогите разобраться как тут транспортная сеть задается

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

Добавлено через 1 минуту
Читайте здесь и здесь.
0
 Аватар для nikola166
10 / 10 / 1
Регистрация: 18.03.2010
Сообщений: 142
17.05.2011, 00:00  [ТС]
что ты мне википедию суешь, я пользоваться поиском умею, я спросил что меня конкретно интересует, а ты мне ересь кидаешь, которой я уже начитался
0
365 / 366 / 167
Регистрация: 11.06.2010
Сообщений: 703
17.05.2011, 00:02
Цитата Сообщение от nikola166 Посмотреть сообщение
и каким образом здесь задается граф и сток и исток, т.е вершины от которой до которой ищем максимальный поток, вроде тут матрицей задается, но что-то она какая то странная
Это вы должны знать, ваш же код

Добавлено через 1 минуту
Цитата Сообщение от nikola166 Посмотреть сообщение
что ты мне википедию суешь, я пользоваться поиском умею, я спросил что меня конкретно интересует, а ты мне ересь кидаешь, которой я уже начитался
Значит плохо читали, там четко написано что такое транспортная сетка.
0
 Аватар для nikola166
10 / 10 / 1
Регистрация: 18.03.2010
Сообщений: 142
17.05.2011, 00:04  [ТС]
Это алгоритм я взял с сайта алгоритмов, если бы я сам это писал я бы не спрашивал
0
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
17.05.2011, 07:10
Цитата Сообщение от 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
2
 Аватар для nikola166
10 / 10 / 1
Регистрация: 18.03.2010
Сообщений: 142
17.05.2011, 22:21  [ТС]
а почему здесь задается еще связь вершины с самой собой
0
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
18.05.2011, 05:13
Цитата Сообщение от nikola166 Посмотреть сообщение
а почему здесь задается еще связь вершины с самой собой
Бывают графы и с петлями. Вы можете задавать вес петле любой (0 или отличный от 0), но на результат это не отразится.
1
 Аватар для nikola166
10 / 10 / 1
Регистрация: 18.03.2010
Сообщений: 142
18.05.2011, 22:57  [ТС]
спасибо за помощь))))))
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
18.05.2011, 22:57
Помогаю со студенческими работами здесь

Объясните, пожалуйста, как идиоту: почему байт в HEX обозначается двумя символами?
И как посчитать его значение, имея на руках только эти два значения? FF == 256, но как это считается? В смысле, без этого X(DEC) == X...

Многопродуктовый поток в графе
Здравствуйте. Необходимо реализовать многопродуктовые потоки на графе. Кто-нибудь может подсказать где поискать информацию по теме?...

Что такое поток в графе
Насколько я знаю, у ребра есть определенная заданная пропускная способность, это единственное, что было понятно. После прочитывания...

Объясните программу для поиска в графе в ширину
Программа для поиска в графе в ширину. Программа рабочая, просто хочу немного разобраться. #include&lt;stdio.h&gt; ...

Объясните программу нахождения эйлерова цикла в неориентированном графе
Помогите объяснить программу. Программу взяла с форума. Необходимо найти эйлеровый цикл в неориентированном графе DOMAINS s=symbol ...


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Новые блоги и статьи
http://iceja.net/ математические сервисы
iceja 20.01.2026
Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .
http://iceja.net/ сервер решения полиномов
iceja 18.01.2026
Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
Расчёт переходных процессов в цепи постоянного тока
igorrr37 16.01.2026
/ * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит переходные токи и напряжения на элементах схемы. . . .
Восстановить юзерскрипты Greasemonkey из бэкапа браузера
damix 15.01.2026
Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений.
anaschu 11.01.2026
https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/
WordPad для Windows 11
Jel 10.01.2026
WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
Classic Notepad for Windows 11
Jel 10.01.2026
Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
Почему дизайн решает?
Neotwalker 09.01.2026
В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru