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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
Astig07
0 / 0 / 0
Регистрация: 02.12.2013
Сообщений: 8
#1

Максимальный поток - лучший алгоритм - C++

02.12.2013, 00:22. Просмотров 1872. Ответов 0
Метки нет (Все метки)

Здравствуйте дорогие форумчане. Давно я не заходил на этот форум. Но столкнулся с небольшой проблемкой. Есть абсолютно работоспособная программа, основная задача которой сводится к нахождению максимального потока в двудольном графе. С одним "но": на программу наложен очень жесткий лимит по времени выполнения. Я попробовал Диница, Форда-Фалкерсона. Но оба они получают TL. Собственно вопрос состоит в том, как оптимизировать эти алгоритмы для уменьшения времени выполнения данной программы или же использовать иной алгоритм. Реализация Форда-Фалкерсона, которую я на данный момент использую:
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
bool bfs(int s, int t, int parent[], int V) // поиск в ширину
{
 
bool visited[V];
memset(visited, 0, sizeof(visited));
 
queue <int> q;
q.push(s);
visited[s] = true;
parent[s] = -1;
 
while (!q.empty())
{
int u = q.front();
q.pop();
 
for (int v=0; v<V; v++)
{
    if (visited[v]==false && graph[u][v] > 0)
    {
        q.push(v);
        parent[v] = u;
        visited[v] = true;
    }
}
}
 
return (visited[t] == true);
}
 
 
int fordFulkerson(int s, int t, int V) // алгоритм нахождения максимального потока
{
int u, v;
 
int parent[V];  
int max_flow = 0;  
 
while (bfs(s, t, parent, V))
{ 
int path_flow = INT_MAX;
for (v=t; v!=s; v=parent[v])
{
    u = parent[v];
    path_flow = min(path_flow, graph[u][v]);
}
 
for (v=t; v != s; v=parent[v])
{
    u = parent[v];
    graph[u][v] -= path_flow;
}
 
max_flow += path_flow;
}
 
 
return max_flow;
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.12.2013, 00:22
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Максимальный поток - лучший алгоритм (C++):

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

Максимальный поток в графе, объясните идиоту - C++
const int inf = 1000*1000*1000; typedef vector&lt;int&gt; graf_line; typedef vector&lt;graf_line&gt; graf; typedef vector&lt;int&gt; vint; ...

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

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

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab () { int s1 = 0; int s2 =...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.12.2013, 00:22
Привет! Вот еще темы с ответами:

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

Какой компилятор лучший - C++
Здравствуйте, дорогие форумчане! Начинаю учебу c++ какие литературы читать и какой компилятор использовать(чаще всего для ООП).

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар) - C++
Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная головоломка). Определение. Перестано́вочные...

Лучший метод это практика да? - C++
Всем привет. Я сейчас изучаю C++(2 книжонки прочитал) делал различные травиальные программки мне стала вся эта теория надаедать хочеться...


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

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

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