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

02.12.2013, 00:22. Показов 8419. Ответов 0

Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам

Здравствуйте дорогие форумчане. Давно я не заходил на этот форум. Но столкнулся с небольшой проблемкой. Есть абсолютно работоспособная программа, основная задача которой сводится к нахождению максимального потока в двудольном графе. С одним "но": на программу наложен очень жесткий лимит по времени выполнения. Я попробовал Диница, Форда-Фалкерсона. Но оба они получают 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;
}

Заказать работу у эксперта

cpp_developer

Эксперт

20123 / 5690 / 1417

Регистрация: 09.04.2010

Сообщений: 22,546

Блог

02.12.2013, 00:22

Ответы с готовыми решениями:

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

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

Алгоритм Форда-Фалкерсона максимальный поток
Для определения потока в сети используют алгоритм Форда-Фалкерсона: а) ищем любую цепь из истока графа в сток; б) каждой дуге...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

raxper

Эксперт

30234 / 6612 / 1498

Регистрация: 28.12.2010

Сообщений: 21,154

Блог

02.12.2013, 00:22

Помогаю со студенческими работами здесь

алгоритм Форда-Фалкерсона максимальный поток
какой компилятор лучше испольковать что бы запустить эту программу > restart:with(networks): >...

Алгоритм Форда-Фалкерсона, максимальный поток в сети
Первое красное значение на пути это вес а второе поток. Проблема заключается в том что поток превышает вес. public class...

Кто предложит лучший алгоритм
Кто предложит лучший алгоритм, данной программы. Ее суть вот в чем вбиваем в поле данные в виде 11/22/33 или 111/35555/111111. И ее нужно...

Как написать лучший алгоритм сжатия
Проснулся сегодня в 5 часов утра, приснилось что я алгоритм сжатия данных придумал, да такой, что можно сжать любой размер до 1го байта, о...

Лучший алгоритм для получения уникального значения
Что лучше md5(time()) или mt_rand(100000000000, 9999999999999) и каков шанс совпадения при mt_rand(100000000000, 9999999999999) ...

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

Или воспользуйтесь поиском по форуму:

Редактор формул (кликните на картинку в правом углу, чтобы закрыть)

Справка по редактору формул

Новые блоги и статьи Все статьи Все блоги /
Нестандартные приемы работы с итераторами в C++ stackOverflow 02.03.2025 Итераторы - один из краеугольных камней C++, предоставляющий универсальный механизм обхода и манипуляции данными в контейнерах. Появившись как замена небезопасным указателям, они эволюционировали от. . .	Лексический анализ и регулярные выражения в C++26 stackOverflow 02.03.2025 Лексический анализ - ядро любого компилятора и инструмента обработки текста. Каждый программист сталкивается с задачами парсинга строк, обработки файлов конфигурации или анализа пользовательского. . .	Подробно о std::mdspan в C++23 stackOverflow 02.03.2025 Работа с многомерными массивами данных традиционно была одной из сложных задач в C++. Программистам приходилось создавать собственные абстракции или использовать сторонние библиотеки для эффективной. . .	Колмогоровская сложность в C++: Путь к совершенному коду stackOverflow 02.03.2025 Абстрактная математическая теория Колмогорова стала мощным средством оценки и улучшения программного кода. Сложность алгоритма - не только в его вычислительной эффективности, но и в том, насколько. . .	Изменения в C# 14 stackOverflow 02.03.2025 Одно из самых значимых изменений в C# 14 - поддержка коллекционных выражений, которые позволяют создавать и инициализировать коллекции с помощью нового лаконичного синтаксиса. Это нововведение. . .
Разработка кроссплатформенного мобильного приложения для iOS/Android на C++ bytestream 02.03.2025 C++ как язык программирования высокого уровня с прямым доступом к аппаратным ресурсам позволяет создавать приложения, работающие одинаково быстро как на iOS, так и на Android устройствах. Ни для кого. . .	Аутентификация/авторизация на Golang bytestream 02.03.2025 Go предлагает множество возможностей для создания надежных систем аутентификации. Встроенные криптографические пакеты, высокая производительность и простота параллельной обработки запросов делают его. . .	Нововведения TypeScript 5.8 bytestream 02.03.2025 TypeScript 5. 8 приносит много возможностей и оптимизаций, которые существенно расширяют границы типобезопасного программирования на JavaScript. Эта версия включает ряд значительных улучшений в работе. . .	Выполнение кода в игровом цикле Unity с использованием не-MonoBehaviour классов C# bytestream 02.03.2025 Обычный подход к разработке игр на Unity тесно связан с использованием MonoBehaviour - базового класса для скриптов, обеспечивающего доступ к игровому циклу через события Update, FixedUpdate и. . .	Управление инстанцированием вложенных классов в C# bytestream 02.03.2025 Вложенные классы в C# - мощное средство для создания тесно связанных типов данных и логики. Такие классы определяются внутри других классов и обеспечивают высокий уровень инкапсуляции, позволяя. . .

Наверх