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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
Gupi
37 / 2 / 1
Регистрация: 05.06.2011
Сообщений: 36
12.04.2014, 08:19     Входные данные. Метод Форда-Фалкерсона #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
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. - макс. поток сети.
Помогите разобраться пожалуйста.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.04.2014, 08:19     Входные данные. Метод Форда-Фалкерсона
Посмотрите здесь:

Разработайте программу обработки массивов. Входные данные введите с клавиатуры. C++
C++ Задача на с++. Сортировка массивов. Входные данные читать из файла!
C++ Сортировка массивов. Входные данные читать из файла
C++ Продумать и задать входные данные так, чтобы был 4-5 альтернатив
C++ Матрица Форда Беллмана и метод Дейкстра
Входные/выходные данные. Метод решения и результат работы C++
Входные данные в функцию C++
Модернизировать программу, чтобы входные данные были многострочными значениями C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
12.04.2014, 12:28     Входные данные. Метод Форда-Фалкерсона #2
тут всё просто в приниципе:сначала вводится кол-во вершин в графе, потом исток и сток, а потом вводится матрица смежности
Gupi
37 / 2 / 1
Регистрация: 05.06.2011
Сообщений: 36
12.04.2014, 18:04  [ТС]     Входные данные. Метод Форда-Фалкерсона #3
А вы можете показать графический пример по этим данным? Получается исток в графе 0?
Yandex
Объявления
12.04.2014, 18:04     Входные данные. Метод Форда-Фалкерсона
Ответ Создать тему
Опции темы

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