33 / 6 / 0
Регистрация: 05.06.2011
Сообщений: 36
1

Входные данные. Метод Форда-Фалкерсона

12.04.2014, 08:19. Показов 5063. Ответов 2
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Доброго времени суток!

Есть код, который работает и справляется с основной задачей - нахождением максимального потока сети методом Форда-Фалкерсона.
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
#include <conio.h>
#include <memory.h>
#include <stdio.h>
using namespace std;
const int max_vershin = 40 ;// максимльное кол-во вершин
 
int number_vershin; // число вершин в графе
const int inf = 10000; // некоторое, условное число обозначающее бесконечность
 
 
//Возьмем  g это будет, массив содержащий текушее значение потока, т.е. g[i][j] это будет поток текущий от вершины i к j
int g[max_vershin][max_vershin];
// А массив k будет содержать вместимости ребер, другими словами k[i][j] будет содержать максимальную величину потока способную течь по ребру (i,j)
int k[max_vershin][max_vershin];
 
//Затем заводим  набор вспомогательных переменных используемых функцией FindPath для обхода в ширину
// переменная fw, это значение потока чарез данную вершину, на данном шаге поиска
int fw[max_vershin];
// link используется для нахождения собственно пути
// link[i] хранит номер предыдущей вешины на пути i к истоку
int link[max_vershin]; 
int course[max_vershin]; //кладем все в очередь
int cb, ct; //Для очереди, заводим вспомогательные переменные cb,ct, где cb - указатель начала очереди и ct - число эл-тов в очереди
 
 
// поск пути по которому возможно пустить поток алгоритмом обхода графа в ширину
// функция будет искать путь из истока в сток по которому еще можно пустить поток,
// считая вместимость ребера (i,j) равной k[i][j] - g[i][j],
// т.е. после каждой итерации(одна итерация - один поиcк пути) уменьшаем вместимости ребер,на величину пущеного потока
int FindPath(int head, int end) // head - исток, end - сток
{
        cb = 0; ct = 1; course[0] = head;
        link[end] = -1; // ставим особую метку для стока
        int i;
        int course_begin; //Вершина
        memset(fw, 0, sizeof(int)*number_vershin); // в начале из всех вершин, кроме истока, течет 0
        fw[head] = inf; // а из истока может вытечь сколько угодно
        while (link[end] == -1 && cb < ct)
        {
                // смотрим какие вершины могут быть достигнуты из начала очереди
                course_begin = course[cb];
                for (i=0; i<number_vershin; i++)
                // проверяем можем ли мы пустить поток по ребру (course_begin,i):
                if ((k[course_begin][i] - g[course_begin][i])>0 && fw[i] == 0) 
                {
                        // если можем, то добавляем i в конец очереди
                        course[ct] = i; ct++;
                        link[i] = course_begin; // указываем, что в i добрались из course_begin
                        // и находим значение потока текущее через вершину i
                        if (k[course_begin][i]-g[course_begin][i] < fw[course_begin])
                             fw[i] = k[course_begin][i];
                        else
                             fw[i] = fw[course_begin];
                }
            cb++;// прерходим к следующей в очереди вершине
        }
        // закончили поиск пути
        if (link[end] == -1) return 0; // мы или не находим путь и выходим
        // или находим:
        // тогда fw[end] будет равен потоку который дотек по данному пути из истока в сток
        // тогда изменяем значения массива g для  данного пути на величину fw[end]
        course_begin = end;
        while (course_begin != head) // путь из стока в исток мы восстанавливаем с помощбю массива link
        {
                g[link[course_begin]][course_begin] +=fw[end];
                course_begin = link[course_begin];
        }
        return fw[end]; // Возвращаем значение потока которое мы еще смогли пустить по графу
}
 
// основная функция поиска максимального потока
int max_fw(int head, int end) // head - исток, end - сток
{
        // инициализируем переменные:
        memset(g, 0, sizeof(int)*max_vershin*max_vershin); // по графу ничего не течет
        int max_fw = 0; // начальное значение потока
        int add_fw;//добавить в поток
        do
        {
                // каждую итерацию ищем какй-либо простой путь из истока в сток
                // и какой еще поток мажет быть пущен по этому пути
                add_fw = FindPath(head, end);
                max_fw += add_fw;
        } while (add_fw >0);// повторяем цикл пока поток увеличивается
        return max_fw;
}
 
int main()
{
   int head, end;
   scanf("%d", &number_vershin);
   scanf("%d %d", &head, &end);
   int i, j;
   for (i=0; i<number_vershin; i++)
      for (j=0; j<number_vershin; j++)
         scanf("%d",&k[i][j]);
 
   printf("%d", max_fw(head, end));
   
  
   _getch();
  
 
}
Основная проблема в том, что я не могу понять что вводится в входных данных.

Например:

6 - это количество вершин.
0 5 - я не могу разобраться, что это за строка и что она показывает.
0 16 0 0 13 0
0 0 12 0 6 0
0 0 0 0 9 20
0 0 7 0 0 4
0 0 0 14 0 0
0 0 0 0 0 0 - Это матрица инцидентности или смежности.
Результат: 23. - макс. поток сети.
Помогите разобраться пожалуйста.
0
12.04.2014, 08:19
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
12.04.2014, 08:19
Ответы с готовыми решениями:

Алгоритм Форда-Фалкерсона
Нужен код алгоритма Форда-Фалкерсона. Нигде не нашел рабочий вариант. А те, что нашел, не работают и содержат кучу мусора.

Алгоритм Форда-Фалкерсона, программа выводит ноль
в чем проблема?вроде матрица инициализируется раз выводит первоначальную матрицу это алгоритм форда-фалкерсона. #include &lt;iostream&gt;...

Входные/выходные данные. Метод решения и результат работы
#include &lt;iostream&gt; #include &lt;cmath&gt; using namespace std; int main() { char i; cin&gt;&gt;i; cout&lt;&lt;&quot;Vvedite bukvu&quot;&lt;&lt;endl; ...

2
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
167 / 167 / 30
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
12.04.2014, 12:28 2
тут всё просто в приниципе:сначала вводится кол-во вершин в графе, потом исток и сток, а потом вводится матрица смежности
1
33 / 6 / 0
Регистрация: 05.06.2011
Сообщений: 36
12.04.2014, 18:04  [ТС] 3
А вы можете показать графический пример по этим данным? Получается исток в графе 0?
0
12.04.2014, 18:04
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
12.04.2014, 18:04
Помогаю со студенческими работами здесь

Алгоритм Форда-Фалкерсона
Здравствуйте дорогие друзья, не завалялась ли у вас где-нибудь реализация данного алгоритма на языке Лисп? Сам на лиспе не программирую и...

Алгоритм Форда-Фалкерсона
Нужно за алгоритмом Форда-Фалкерсона рассщитать максимальный поток транспортной сети(вложение). Помогите пожалуйста а то у меня не...

Теорема Форда-Фалкерсона
Здравствуйте всем, не получается разобраться с этой теоремой. Не понятно в одном моменте, в теореме сказано что 1. Поток f максимален. ...

алгоритм форда-фалкерсона
Доброго времени суток, как можно реализовать алгоритм Форда-Фалкерсона в матрице? Размер матрицы может изменятся в зависимости от числа...

Реализация алгоритма Форда-Фалкерсона
Есть готовый код программы ?


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему

Редактор формул (кликните на картинку в правом углу, чтобы закрыть)
Опции темы

Новые блоги и статьи
Использование кэша Laravel - полный гайд
bytestream 18.02.2025
Кэширование - один из наиболее эффективных способов повышения производительности веб-приложений. В современном мире, где скорость загрузки страниц напрямую влияет на удержание пользователей и. . .
Создаем REST API в Laravel с аутентификацией через Passport
bytestream 18.02.2025
Разработка современных веб-приложений все чаще требует создания надежного и хорошо структурированного API. REST API стал стандартом де-факто для построения взаимодействия между клиентской и серверной. . .
Пайплайны в Laravel - полный гайд
bytestream 18.02.2025
Разработка современных веб-приложений часто требует обработки сложных процессов, состоящих из множества последовательных шагов. Например, при создании системы комментариев может потребоваться. . .
Как правильно использовать @required в Symfony
bytestream 18.02.2025
При разработке приложений на Symfony мы часто сталкиваемся с необходимостью внедрения зависимостей. Фреймворк предоставляет несколько способов управления этим процессом, и одним из таких инструментов. . .
Система безопасности в Laravel: возможности и примеры
Wired 18.02.2025
Каждый день появляются новые виды атак и уязвимостей, которые могут поставить под угрозу конфиденциальные данные пользователей и функционирование всей системы. В этом контексте выбор надежного. . .
Давайте сравним Django и Laravel
Wired 18.02.2025
Django и Laravel - два мощных инструмента, которые часто сравнивают между собой. Оба фреймворка предлагают разработчикам богатый набор возможностей для создания масштабируемых веб-приложений, но. . .
Laravel или React - что лучше?
Wired 18.02.2025
В разработке веб выбор правильного инструмента часто определяет успех всего проекта. Особенно интересным представляется сравнение Laravel и React - двух популярных технологий, которые часто. . .
Laravel 11: новые возможности, гайд по обновлению
Wired 18.02.2025
Laravel 11 - это новая масштабная версия одного из самых популярных PHP-фреймворков, выпущенная в марте 2024 года. Эта версия продолжает традицию внедрения передовых технологий и методологий. . .
Миграции в Laravel
Wired 18.02.2025
Разработка веб-приложений на Laravel неразрывно связана с управлением структурой базы данных. При работе над проектом часто возникает необходимость вносить изменения в схему базы данных - добавлять. . .
Аутентификация в Laravel
Wired 18.02.2025
В современном мире веб-разработки безопасность пользовательских данных становится критически важным аспектом любого приложения. Laravel, как один из самых популярных PHP-фреймворков, предоставляет. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru