Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
c++\noob
-2 / 2 / 0
Регистрация: 13.11.2010
Сообщений: 52
#1

Графы. Поток минимальной стоимости - C++

20.12.2012, 14:04. Просмотров 1057. Ответов 0
Метки нет (Все метки)

Помогите кто может сделать тестовый пример для данной программы. Что-то не выходит у меня с вводом и выводом: данные читаются из файла(Input), результат записывается в файл(Output).

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#include <vector>
#include <algorithm>
 
using namespace std;
 
// это типа бесконечность будет
const int inf = 0x3fffffff;
 
/* структура, олицетворяющая одно ребро */
struct Edge
{
    int next;           // номер вершины, в которую идет ребро
    int inv;            // номер обратного к данному ребру ребра, нумерация конечно в списке вершины next
    int flow;           // текущий поток
    int cap;            // пропускная способность ребра
    int cost;           // стоимость потока по данному ребру
 
    /* конструктор - задаёт все параметры, кроме текущего потока, который
    выставляется сначала как нулевой */
    Edge(int next, int inv, int cap, int cost) : next(next), inv(inv), flow(0), cap(cap), cost(cost) {}
};
 
/* структура, олицетворяющая граф, с которым будем работать */
struct Graph
{
    int n;              // количество вершин в графе
    vector<vector<Edge> > e;    // исходящие ребра, соответственно по одному вектору ребер на каждую вершину
    vector<int> phi;        // вектор потенциалов, по одному потенциалу на каждую вершину :)
    vector<int> d;          // вектор текущих расстояний для алгоритма Дейкстры
    vector<int> f;          // вектор флажков для алгоритма Дейкстры
    vector<int> from;       // вектор, по которому восстанавливается путь после алгоритма Дейкстры; точное
                                                        // определение - номер ребра в списке ребер для данной вершины, по которому
                                                        // надо перейти, чтобы попасть в вершину-предшественника
 
    /* создать граф с n вершинами - просто инициализирует все векторы нужным количеством объектов */
    Graph(int n) : n(n), e(n), phi(n), d(n), f(n), from(n) {}
 
    /* добавить ребро графа; в действительности добавляет два ребра - прямое и обратное */
    void AddEdge(int a, int b, int cap, int cost)
    {
        // добавить прямое ребро
        e[a].push_back(Edge(b, e[b].size(), cap, cost));
        // добавить обратное ребро
        e[b].push_back(Edge(a, e[a].size() - 1, 0, -cost));
        /* почему inv для ребер устанавливается именно так? inv - это номера ребер в соответствующих
        векторах. В первой строке - e[b].size(), так как во второй строке новое ребро получит именно
        этот номер. Во второй строке - e[a].size() - 1, так как прямое ребро уже создано, и
        уже получило соответствующий номер */
    }
 
    /* Найти максимальный поток минимальной стоимости!!!
    source - номер вершины-истока, sink - номер вершины-стока
    возвращать результат будем в паре (поток; стоимость) */
    pair<int, int> MinCostMaxFlow(int source, int sink)
    {
        /* выполнить начальное назначение потенциалов
        с помощью алгоритма Беллмана-Форда.
        Проще говоря, начальные потенциалы вершин - это кратчайшие
        расстояния до вершин от истока, если считать длинами ребер
        их стоимости; причем учитываются только прямые ребра.
        Если ребер отрицательной стоимости в графе нет,
        то следующий блок можно (и нужно) выкидывать :) */
        {
            // залить потенциалы бесконечностями
            fill(phi.begin(), phi.end(), inf);
            // только истоку задать 0
            phi[source] = 0;
            // по алгоритму нужно все тупо повторить n раз
            for(int i = 0; i < n; ++i)
                // перебор вершины
                for(int j = 0; j < n; ++j)
                    // если она уже получила потенциал
                    if(phi[j] < inf)
                        // перебор исходящих из вершины ребер
                        for(int k = 0; k < e[j].size(); ++k)
                            // если ребро - прямое, и позволяет улучшить оценку расстояния до вершины на ее конце
                            if(e[j][k].cap > 0 && phi[e[j][k].next] > phi[j] + e[j][k].cost)
                                // улучшить эту оценку
                                phi[e[j][k].next] = phi[j] + e[j][k].cost;
        }
 
        // переменные для ответа
        int resultFlow = 0, resultCost = 0;
 
        /* вооот... только сейчас начинается основной алгоритм :)
        цикл, на каждой итерации которого выполняется поиск увеличивающего пути
        и собственно увеличение потока по этому пути */
        for(; ; )
        {
            // обнулить флажки
            fill(f.begin(), f.end(), 0);
            // установить расстояние до всех вершин равным бесконечности
            fill(d.begin(), d.end(), inf);
            // кроме, конечно, истока
            d[source] = 0;
 
            // цикл алгоритма Дейкстры
            for(; ; )
            {
                // найти непомеченную вершину с наименьшим расстоянием до истока
                int i = -1;
                for(int j = 0; j < n; ++j)
                    if(!f[j] && d[j] < inf && (i < 0 || d[i] > d[j]))
                        i = j;
                // если такой вершины нет, то, значит, все вершины или помечены, или недостижимы
                // завершаем алгоритм Дейкстры
                if(i < 0) break;
 
                // помечаем найденную вершину
                f[i] = 1;
 
                // перебираем исходящие из нее ребра
                for(int j = 0; j < e[i].size(); ++j)
                    // рассматриваем только те ребра, по которым можно протолкнуть поток
                    if(e[i][j].cap > e[i][j].flow)
                    {
                        // получить вершину на другом конце ребра
                        int a = e[i][j].next;
                        // проверить, что она непомечена, и можно улучшить оценку расстояния до нее
                        // расстояние проверяется с учетом потенциалов!
                        if(!f[a] && d[a] > d[i] + e[i][j].cost + phi[i] - phi[a])
                        {
                            // улучшаем оценку расстояния
                            d[a] = d[i] + e[i][j].cost + phi[i] - phi[a];
                            // указываем для нее вершину-предшественника (вернее, как уже говорилось,
                            // номер ребра, перейдя по которому, мы придем в предшественника)
                            from[a] = e[i][j].inv;
                        }
                    }
            }
 
            // все, алгоритм Дейкстры вычислил кратчайшие пути
            // если при этом он не дошел до стока, то, значит, увеличивающих
            // путей больше нет; завершаем алгоритм
            if(!f[sink]) break;
 
            // выполняем обновление потенциалов
            for(int i = 0; i < n; ++i)
                // в зависимости от того, достигнута ли вершина, прибавляем к ее потенциалу добавку
                phi[i] += f[i] ? d[i] : d[sink];
 
            // определяем, насколько мы на этот раз можем увеличить поток
            // и сколько нам это стоило
            int augFlow = inf, augCost = 0;
            // для этого надо пройтись по найденному увеличивающему пути
            // и поглядеть, сколько можно протолкнуть потока
            // так как у нас сохранены предшественники, то идем от стока к истоку
            // т.е. как бы задом наперед
            for(int i = sink; i != source; )
            {
                // получить вершину, из которой мы пришли в вершину i
                int a = e[i][from[i]].next;
                // получить ребро, по которому мы пришли из вершины a в вершину i
                int b = e[i][from[i]].inv;
 
                // ограничить новый поток, если надо
                // cap - flow - это максимальный добавочный поток, который мы
                // можем протолкнуть через данное ребро
                augFlow = min(augFlow, e[a][b].cap - e[a][b].flow);
                // суммировать стоимость потока
                augCost += e[a][b].cost;
 
                // перейти дальше "назад"
                i = a;
            }
 
            // теперь мы вычислили, сколько потока мы можем сейчас протолкнуть
            // скорректировать информацию в ребрах с помощью еще одного прохода
            for(int i = sink; i != source; )
            {
                // получить вершину, из которой мы пришли в вершину i
                int a = e[i][from[i]].next;
                // получить ребро, по которому мы пришли из вершины a в вершину i
                int b = e[i][from[i]].inv;
 
                // добавить поток к прямому ребру
                e[a][b].flow += augFlow;
                // соответственно убавить поток от обратного ребра
                e[i][from[i]].flow -= augFlow;
 
                // перейти дальше "назад"
                i = a;
            }
 
            // осталось только добавить наши достижения к счетчикам
            resultFlow += augFlow;
            // стоимость потока взимается за каждую единицу потока!
            resultCost += augFlow * augCost;
        }
 
        //вернуть ответ
        return make_pair(resultFlow, resultCost);
    }
    
 };
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.12.2012, 14:04
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Графы. Поток минимальной стоимости (C++):

Поток минимальной стоимости - C++
Дискретка : графы . Задача: существуют два города A и B , города соединены между собой сетью дорог проходящих так же через города...

Графы. Найти систему нефтепроводов минимальной суммарной стоимости - C++
Подскажите с чего вообще начать? Нужно решить с помощью графа.

Максимальный поток минимальной стоимости - C++
Вечер добрый, нашел программу работает, выдает как я понял максимальный поток и минимальную стоимость. Вопрос в следующем, как там матрица...

Помогите доделать программу определения минимальной стоимости билета. - C++
Определить минимальную стоимость билета для пассажира, следующего на заданное расстояние, стоимость билета с учетом выбранного вида...

Скопировать поток и добавить ошибки в поток - C++
Здорова господа! Есть задачка: &quot;Скопируйте поток объектов типа Name_and_address и вставьте в него столько ошибок, сколько сколько...

Нужно создать базу данных (создать пустой бинарный файл). Через поток. Поток бинарного файла описать в виде локальной переменной внутри функции. - C++
Совсем не понял эту тему. Нужно создать базу данных (создать пустой бинарный файл). Через поток. Поток бинарного файла описать в виде...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.12.2012, 14:04
Привет! Вот еще темы с ответами:

Скопировать поток в поток - C++
Есть ли возможность скопировать один поток в другой. Например int main() { ofstream (*P) = new ofstream; ofstream...

Поток минимальной стоимости в Маткаде - MathCAD
День добрый уважаемые коллеги. Есть готовая написанная программа для нахождения потока минимальной стоимости(транспортная задача). Но есть...

Нахождение пути минимальной стоимости? - C (СИ)
Задача такая, есть матрица размером m на n. Необходимо из нижнего левого угла попасть в верхний правый с минимальным количеством шагов....

Выбор минимальной стоимости компьютерных комплектующих - MS Access
Есть несколько таблиц, в которых хранятся списки компьютерных комплектующих со своими некоторыми параметрами и ценой(таблица процессоров,...


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

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

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