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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Для каждой из матриц подсчитать количество четных элементов в каждой строке http://www.cyberforum.ru/cpp-beginners/thread1025154.html
даны 2 матрицы разн.размерности. Для каждой из них подсчитать кол-во четных эл-тов в каждой строке. Использовать процедуры и ф-ции.
C++ сортировка массива это код сортировки массива: #include <iostream> #include <conio.h> using namespace std; int main() {int mass; int iteracia=0; for (int i=0;i<5;i++) http://www.cyberforum.ru/cpp-beginners/thread1025151.html
Как описывать множества, пересекать их, складывать C++
Расскажите, как описывать множества, пересекать их, складывать и т.д. Искал в гугле, но не нашел ничего путного
Сформировать одномерный массив целых чисел C++
1.Сформировать одномерный массив целых чисел. 2.Распечатать полученный массив. 3.Удалить элементы,индексы которых кратны 3. 4.Добавить после каждого отрицательного элемента M массива элемент со значением M-1. 5.Распечатать полученный массив. Программу надо написать используя вектор.
C++ Вывести все буквы/цифры, которые НЕ входят в текст http://www.cyberforum.ru/cpp-beginners/thread1025115.html
доброго здоровья, уважаемые! есть условие: в файле задан любой текст/цифры... нужно вывести все буквы/цифры, которые НЕ входят в этот текст... (надеюсь она не большая)
C++ Возвращение значения из рекурсивной функции Всем добрый вечер! Есть функция последовательного обхода графа по вершинам для определения в нем циклов.(если можно дойти из вершины каким-либо путем, не проходя по уже пройденным ребрам, то цикл есть). Реализовать нужно, используя именно рекурсию. Фиксируем вершину и ищем цикл, если он есть(упираемся в нижний уровень рекурсии) то мы должны присвоить b=false и возвратить это значение, но... подробнее

Показать сообщение отдельно
Astig07
0 / 0 / 0
Регистрация: 02.12.2013
Сообщений: 8
02.12.2013, 00:22     Максимальный поток - лучший алгоритм
Здравствуйте дорогие форумчане. Давно я не заходил на этот форум. Но столкнулся с небольшой проблемкой. Есть абсолютно работоспособная программа, основная задача которой сводится к нахождению максимального потока в двудольном графе. С одним "но": на программу наложен очень жесткий лимит по времени выполнения. Я попробовал Диница, Форда-Фалкерсона. Но оба они получают 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;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 15:09. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru