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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
Astig07
0 / 0 / 0
Регистрация: 02.12.2013
Сообщений: 8
02.12.2013, 00:22     Максимальный поток - лучший алгоритм #1
Здравствуйте дорогие форумчане. Давно я не заходил на этот форум. Но столкнулся с небольшой проблемкой. Есть абсолютно работоспособная программа, основная задача которой сводится к нахождению максимального потока в двудольном графе. С одним "но": на программу наложен очень жесткий лимит по времени выполнения. Я попробовал Диница, Форда-Фалкерсона. Но оба они получают 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.12.2013, 00:22     Максимальный поток - лучший алгоритм
Посмотрите здесь:

C++ Максимальный поток в графе, объясните идиоту
Дуэль на лучший рисунок (изображение) в C++ C++
Посоветуйте лучший справочник по С++ C++
Какой компилятор лучший C++
C++ Лучший метод это практика да?
C++ Скопировать поток в поток
C++ Максимальный поток минимальной стоимости
Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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