Форум программистов, компьютерный форум, киберфорум
Дискретная математика
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.64/11: Рейтинг темы: голосов - 11, средняя оценка - 4.64
0 / 0 / 0
Регистрация: 18.12.2013
Сообщений: 43
1

Построить максимальный поток графа по алгоритму Форда-Фулкерсона

02.06.2014, 15:57. Показов 2171. Ответов 3
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Здравствуйте, помогите построить максимальный поток графа по алгоритму форда-фулкерсона. Сам не смог разобраться. Граф я строил из матрицы весов, которая была дана изначально, а теперь не знаю как строить максимальный поток и указать срез. Помогите! Пожалуйста!
Миниатюры
Построить максимальный поток графа по алгоритму Форда-Фулкерсона  
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.06.2014, 15:57
Ответы с готовыми решениями:

Минимальный и максимальный путь по алгоритму Беллмана-Калаба и Форда
Добрый день ,не работает код который считывает минимальный и максимальный путь по алгоритму...

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

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

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

3
24 / 24 / 12
Регистрация: 04.06.2014
Сообщений: 80
07.06.2014, 03:33 2
написать программу, или показать как решить руками?

Добавлено через 6 минут
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
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
 
const int inf = 1000*1000*1000;
 
int main(){
    int n,m,u,v,w,s,t;
    scanf("%d%d",&n,&m);
    int c[11][11],f[11][11];
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j)
            c[i][j] = f[i][j] = 0;
    for (int i=0;i<m;++i){
        scanf("%d%d%d",&u,&v,&w);
        c[u][v] = w;
    }
    scanf("%d%d",&s,&t);
    for (;;){
        vector < int > p(11),cf(11);
        queue < int > q;
        q.push(s); cf[s] = inf;
        while (!q.empty()){
            int v = q.front();
            for (int i=1;i<=n;++i){
                if (!p[i] && c[v][i] - f[v][i] > 0){
                    q.push(i);
                    p[i] = v;
                    cf[i] = min(cf[v],c[v][i] - f[v][i]);
                }
            }
            q.pop();
        }
        if (!p[t])  break;
        for (int u=t;u != s;u = p[u]){
            f[p[u]][u] += cf[t];
            f[u][p[u]] -= cf[t];
        }
    }
    long long flow = 0;
    for (int i=1;i<=n;++i)
        if (c[s][i] > 0)
            flow += f[s][i];
    printf("%d\n",flow);
}
1
0 / 0 / 0
Регистрация: 10.12.2012
Сообщений: 27
27.11.2014, 21:41 3
а можете не программой а так объяснить? нарисовать
0
24 / 24 / 12
Регистрация: 04.06.2014
Сообщений: 80
28.11.2014, 02:38 4
https://www.youtube.com/watch?v=yUFnDj4NH6c
0
28.11.2014, 02:38
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.11.2014, 02:38
Помогаю со студенческими работами здесь

Максимальный поток графа
Написал программу для поиска максимального потока в графе. На сайте mmccme.ru некоторые тесты не...

Максимальный поток между вершинами графа
Признаться, не срослось у меня с математикой в ВУЗе. Не то что бы идиот: просто учился в...

Нахождение минимального пути по алгоритму Форда-Беллмана
Помогите пожалуйста. Не могу понять как выбрать из какой вершины в какую идти.

Алгоритм Форда Беллмана для НЕориентированного взвешенного графа
Имеется задание - найти минимальный путь с вершины V0 в вершину V4 с помощью алгоритма Форда...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru