Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
bikovbiv
3 / 3 / 0
Регистрация: 21.02.2016
Сообщений: 75
1

Форд-Фалкерсон, ошибка в программе после избавлени от глобальных переменных

16.05.2018, 03:15. Просмотров 340. Ответов 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
#include <iostream>
#include <queue>
#include <vector>
#define sz 25
 
class Helper
{
public:
    char sink;
    char source;
    std::vector<std::vector<int>> currentFlow;
    std::vector<std::vector<int>> adjacencyMatrix;
    Helper() :  sink(0), source(0), currentFlow(sz, std::vector<int>(sz, -1)), adjacencyMatrix(sz, std::vector<int>(sz, 0)) {}
 
void fill_adj_matrix(int i, int j, int w)
{
    adjacencyMatrix[i][j] = w;
}
    
int Ford_Falkerson()
{
    std::vector<int> flow_vert(sz, 0);
    std::vector<int> came_from(sz, 0);
    std::queue <char> queue;
    char temp_vert;
    flow_vert [(int)(source - 'a')] = 9999;
    came_from[(int)(sink - 'a')] = 0;
    queue.push(source);
    while (came_from[(int)(sink - 'a')] == 0 && !queue.empty()) {
        temp_vert = queue.front();
         for (int j = 0; j < sz; j++){
                if ((adjacencyMatrix[(int)(temp_vert - 'a')][j] - currentFlow[(int)(temp_vert - 'a')][j])>0 && flow_vert[j] == 0) {
                        queue.push((char)(j+'a'));
                        came_from[j] = temp_vert;
                        flow_vert[j] = std::min(flow_vert[(int)(temp_vert-'a')], adjacencyMatrix[(int)(temp_vert - 'a')][j]
                        - currentFlow[(int)(temp_vert - 'a')][j]);
                }
         }
        queue.pop();
    }
    if (came_from[(int)(sink-'a')] == 0)
        return 0;
    temp_vert = sink;
    while ( temp_vert != source ) 
    {
         currentFlow [(int)(came_from[(int)(temp_vert - 'a')] - 'a')][(int)(temp_vert - 'a')] += flow_vert [(int)(sink - 'a')];
         currentFlow [(int)(temp_vert - 'a')][(int)(came_from[(int)(temp_vert - 'a')] - 'a')] -= flow_vert [(int)(sink - 'a')];
         temp_vert = came_from [(int)(temp_vert - 'a')];
    }
    return flow_vert [(int)(sink-'a')];
}
 
int max_flow ()
{
    int new_flow = Ford_Falkerson();
    int sum = new_flow;
    while (new_flow > 0)
    {
        new_flow = Ford_Falkerson();
        sum += new_flow;
    }
    return sum;
}
    
void out()
{
    //std::cout << max_flow(); << std::endl;
    for (int i = 0; i < sz; i++)
    {
        for (int j = 0; j < sz; j++)
        {
            if (currentFlow[i][j] != -1 && currentFlow[i][j] < 0 )
                currentFlow[i][j] = 0;
            if ((currentFlow[i][j]!=-1) && adjacencyMatrix[i][j] != 0)
                std::cout << (char)(i + 'a') << ' ' << (char)(j + 'a')
                << ' ' << currentFlow[i][j] << std::endl;
        }
    }
}
 
};
 
int main()
{
    int n = 0, weight;
    Helper h;
    char a, b;
    //h.out_2();
    std::cin >> n >> h.source >> h.sink;
    for (int m = 0; m < n; m++)
    {
        std::cin >> a >> b >> weight;
        int i = a - 'a';
        int j = b - 'a';
        //h.adjacencyMatrix[i][j] = weight;
        h.fill_adj_matrix(/*(int)(a - 'a'), (int)(b - 'a')*/i,j, weight);
    }
    std::cout << h.max_flow() << std::endl;
    h.out();
    //h.out_2();
    return 0;
}
Ранее класса не было, потом создал его, перенес туда std::vector<std::vector<int>> currentFlow;
std::vector<std::vector<int>> adjacencyMatrix; и функции, собственно думаю, что проблема связана с двумя этими массивами, но что именно - не понимаю. Прошу помощи
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.05.2018, 03:15
Ответы с готовыми решениями:

Ошибка в сравнении глобальных переменных в функциях
Здравствуйте! Я всю жизнь писал на Pascal и с С столкнулся впервые пару дней назад, когда начал...

Алгоритм Форд-Фалкерсон
&gt; restart:with(networks): &gt; new(G):V:=$1..14:addvertex(,G): &gt; v1:=1:#источник &gt; v2:=14:#сток &gt;...

Количество глобальных переменных в программе
Всем привет. Давно хотел спросить про количество глобальных переменных в программе. Натыкался на...

Рассмотреть программу, написать имена глобальных переменных, локальных переменных, формальных параметров
Program P1; var s:string; procedure P(var s:string) ; var i, j : integer; ...

О глобальных переменных
Народ всем привет! Я только начал программировать на Visual Basic 2005 express edition. Помогите с...

1
bikovbiv
3 / 3 / 0
Регистрация: 21.02.2016
Сообщений: 75
17.05.2018, 15:06  [ТС] 2
Тема закрыта, ошибку нашел, почему-то проинициализировал curentFlow -1, нужно нулями
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.05.2018, 15:06

Сброс глобальных переменных
Есть программа, в которой из за моей криворукости используется очень много глобальных переменных....

Описание глобальных переменных
помогите, плиз, с такой незадачей.. в каком из файлов нужно обозначить глобальные переменные, чтоб...

Определение глобальных переменных
Где можно определять глобальные переменные. Причина тому, что надо считывать с формы такие значения...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru