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

Программа поиска максимального потока методом Форда-Фалкерсона. НЕОБХОДИМО РАЗОБРАТЬ В ЧЕМ ОШИБКА С scanf?

23.12.2019, 12:36. Показов 1277. Ответов 0

Студворк — интернет-сервис помощи студентам
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
#include <memory.h>
#include <stdio.h>
 
const int MAX_VERTICES = 40;
 
int NUM_VERTICES; // число вершин в графе
const int INFINITY = 10000; // условное число обозначающее бесконечность
 
// f - массив садержащий текушее значение потока
// f[i][j] - поток текущий от вершины i к j
int f[MAX_VERTICES][MAX_VERTICES];
// с - массив содержащий вместимоти ребер,
// т.е. c[i][j] - максимальная величину потока способная течь по ребру (i,j)
int c[MAX_VERTICES][MAX_VERTICES];
 
// набор вспомогательных переменных используемых функцией FindPath - обхода в ширину
// Flow - значение потока чарез данную вершину на данном шаге поиска
int Flow[MAX_VERTICES];
// Link используется для нахождения собственно пути
// Link[i] хранит номер предыдущей вешины на пути i -> исток
int Link[MAX_VERTICES]; 
int Queue[MAX_VERTICES]; // очередь
int QP, QC; // QP - указатель начала очереди и QC - число эл-тов в очереди
 
// поск пути по которому возможно пустить поток алгоритмом обхода графа в ширину
// функция ищет путь из истока в сток по которому еще можно пустить поток,
// считая вместимость ребера (i,j) равной c[i][j] - f[i][j],
// т.е. после каждой итерации(одна итерация - один поик пути) уменьшаем вместимости ребер,
// на величину пущеного потока
int FindPath(int source, int target) // source - исток, target - сток
{
        QP = 0; QC = 1; Queue[0] = source;
        Link[target] = -1; // особая метка для стока
        int i;
        int CurVertex;
        memset(Flow, 0, sizeof(int)*NUM_VERTICES); // в начале из всех вершин кроме истока течет 0
        Flow[source] = INFINITY; // а из истока может вытечь сколько угодно
        while (Link[target] == -1 && QP < QC)
        {
                // смотрим какие вершины могут быть достигнуты из начала очереди
                CurVertex = Queue[QP];
                for (i=0; i<NUM_VERTICES; i++)
                // проверяем можем ли мы пустить поток по ребру (CurVertex,i):
                if ((c[CurVertex][i] - f[CurVertex][i])>0 && Flow[i] == 0) 
                {
                        // если можем, то добавляем i в конец очереди
                        Queue[QC] = i; QC++;
                        Link[i] = CurVertex; // указываем, что в i добрались из CurVertex
                        // и находим значение потока текущее через вершину i
                        if (c[CurVertex][i]-f[CurVertex][i] < Flow[CurVertex])
                             Flow[i] = c[CurVertex][i];
                        else
                             Flow[i] = Flow[CurVertex];
                }
            QP++;// прерходим к следующей в очереди вершине
        }
        // закончив поиск пути
        if (Link[target] == -1) return 0; // мы или не находим путь и выходим
        // или находим:
        // тогда Flow[target] будет равен потоку который "дотек" по данному пути из истока в сток
        // тогда изменяем значения массива f для  данного пути на величину Flow[target]
        CurVertex = target;
        while (CurVertex != source) // путь из стока в исток мы восстанавливаем с помощбю массива Link
        {
                f[Link[CurVertex]][CurVertex] +=Flow[target];
                CurVertex = Link[CurVertex];
        }
        return Flow[target]; // Возвращаем значение потока которое мы еще смогли "пустить" по графу
}
 
// основная функция поиска максимального потока
int MaxFlow(int source, int target) // source - исток, target - сток
{
        // инициализируем переменные:
        memset(f, 0, sizeof(int)*MAX_VERTICES*MAX_VERTICES); // по графу ничего не течет
        int MaxFlow = 0; // начальное значение потока
        int AddFlow;
        do
        {
                // каждую итерацию ищем какй-либо простой путь из истока в сток
                // и какой еще поток мажет быть пущен по этому пути
                AddFlow = FindPath(source, target);
                MaxFlow += AddFlow;
        } while (AddFlow >0);// повторяем цикл пока поток увеличивается
        return MaxFlow;
}
 
int main()
{
   int source, target;
   scanf("%d", &NUM_VERTICES);
   scanf("%d %d", &source, &target);
   int i, j;
   for (i=0; i<NUM_VERTICES; i++)
      for (j=0; j<NUM_VERTICES; j++)
         scanf("%d",&c[i][j]);
 
   printf("%d", MaxFlow(source, target));
   return 0;
}
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
23.12.2019, 12:36
Ответы с готовыми решениями:

Поиск максимального потока методом Форда-Фалкерсона
Здрасвуйте помогите мне пожалуйста найти поиск максимального потока методом Форда-Фалкерсона; для поиска дополняющего пути используется...

Алгоритм Форда-Фалкерсона. Нахождение максимального потока сети
В одном из городов имеется производство обуви на экспорт. Вся обувь отправляется диллерам морским путем через один и тот же порт. Для...

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

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
23.12.2019, 12:36
Помогаю со студенческими работами здесь

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Новые блоги и статьи
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .
Символьное дифференцирование
igorrr37 13.02.2026
/ * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru