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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 29, средняя оценка - 4.66
Mysterion777
-74 / 48 / 2
Регистрация: 11.01.2013
Сообщений: 199
#1

алгоритм Форда-Фалкерсона - C++

29.05.2013, 12:06. Просмотров 4168. Ответов 0
Метки нет (Все метки)

Есть алгоритм Форда Фалкерсона, не пойму как восстановить сам поток пот точкам или ребрам чтобы отобразить его графически, не могу сообразить как.
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
входные данные
7
0 10 5 0 0 8 0
0 0 0 5 3 0 4
0 0 0 4 5 10 0
0 0 0 0 4 0 9
0 0 0 0 0 5 6
0 0 0 0 0 0 7
0 0 0 0 0 0 0
 
#include "stdio.h"
#include "conio.h"
#include "iostream"
 
using namespace std;
 
#define WHITE 0
#define GREY 1
#define BLACK 2
 
int n,e;
int capacity[100][100], // Матрица пропускных способнотей
 flow[100][100],  // Матрица потока
 color[100],      // Цвета для вершин
 pred[100];       // Массив пути
 int head, tail;  // Начало, Конец
 int q[102];      // Очередь, хранящая номера вершин входящих в неё
 
// Сравнение двух целых значений 
    int min(int x, int y)
{
  if (x < y)
    return x;
  else
    return y;
}
 
// Добавить в очередь (мы ступили на вершину) 
    void enque(int x)
{
  q[tail] = x;     // записать х в хвост
  tail++;          // хвостом становиться следующий элемент
  color[x] = GREY; // Цвет серый (из алгоритма поиска)
}
 
// Убрать из очереди (Вершина чёрная, на неё не ходить) 
    int deque()
{
  int x = q[head];  // Записать в х значение головы
  head++;           // Соответственно номер начала очереди увеличивается
  color[x] = BLACK; // Вершина х - отмечается как прочитанная
  return x;         // Возвращается номер х прочитанной вершины
}
 
// Поиск в ширину 
    int bfs(int start, int end)
{
  int u,v;
  for( u = 0; u < n; u++ ) // Сначала отмечаем все вершины не пройденными
    color[u]=WHITE;   
 
  head=0;   // Начало очереди 0
  tail=0;   // Хвост 0
  enque(start);      // Вступили на первую вершину
  pred[start]= -1;   // Специальная метка для начала пути
  while(head!=tail)  // Пока хвост не совпадёт с головой
  {
    u=deque();       // вершина u пройдена
    for( v = 0; v < n; v++ ) // Смотрим смежные вершины
    {
     // Если не пройдена и не заполнена
     if(color[v] == WHITE && (capacity[u][v]-flow[u][v]) > 0) {
       enque(v);  // Вступаем на вершину v
       pred[v]=u; // Путь обновляем
     }
    }
  }  
  if(color[end] == BLACK) // Если конечная вершина, дошли - возвращаем 0
    return 0;
  else return 1;
}
 
// Максимальный поток из истока в сток 
int max_flow(int source, int stock)
{
  int i,j,u;
  int maxflow=0;            // Изначально нулевой
  for( i = 0; i < n; i++ )  // Зануляем матрицу потока
    {
      for( j = 0; j < n; j++)
      flow[i][j]=0;
    }
  while(bfs(source,stock) == 0)             // Пока сеществует путь
    {
      int delta=10000;
      for(u = n-1; pred[u] >= 0; u=pred[u]) // Найти минимальный поток в сети
      {
        delta=min(delta, ( capacity[pred[u]][u] - flow[pred[u]][u] ) );
      }
      for(u = n-1; pred[u] >= 0; u=pred[u]) // По алгоритму Форда-Фалкерсона 
      {     
        flow[pred[u]][u] += delta;
        flow[u][pred[u]] -= delta;
      }
      maxflow+=delta;                       // Повышаем максимальный поток
    }
  return maxflow;
}
 
// Описав все эти предварительные функции, можем кратко оформить функцию main().
// Данные считаем из файла.
    int main()
{
  setlocale(LC_ALL, "Russian");       // установка вывода (не ввода) русского языка в консоли (только Visual Studio)
   
  // Чтение из файла
  freopen ("input.txt", "r", stdin);  // аргумент 1 - путь к файлу, 2 - режим ("r" || "w"), 3 - stdin || stdout
  cin >> n;
  cin>>e;
  cout << "Количество вершин: " << n << endl;  
  int i,j;
  for( i = 0; i < n; i++ )
    {
      for( j = 0; j < n; j++ )
        capacity[i][j]=0;
    }
  for (i=0; i<e; i++) {
      int a,b,c;
    cin>>a>>b>>c;
    capacity[a-1][b-1] = c;
    }  
 
  cout << "Максимальный поток: " << max_flow(0,n-1) << endl;
  cout << "Матрица чего-то там: " << endl;
    for( i = 0; i < n; i++ ) 
    {
      for( j = 0; j < n; j++ )
        cout << flow[i][j] << " ";
      cout << endl;
    }
 
  _getche();
  return 0;
}
Добавлено через 1 час 31 минуту
Сделал так не знаю правильно или нет.
Java
1
2
3
4
5
6
7
8
9
10
11
12
    
// сделал динамичский массив и потом между вершинами
// i floww[i] закрашивал поток типо он между ними проходит 
private ArrayList <Integer>
 int delta=10000;
          for(u = n-1; pred[u] >= 0; u=pred[u]) // Найти минимальный поток в сети
          {
              floww.add(pred[u]);
              floww.add(u);
             // System.out.println(pred[u]+" "+u+" - ");
            delta=min(delta, ( capacity[pred[u]][u] - flow[pred[u]][u] ) );
          }
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.05.2013, 12:06
Здравствуйте! Я подобрал для вас темы с ответами на вопрос алгоритм Форда-Фалкерсона (C++):

Алгоритм Форда-Фалкерсона, программа выводит ноль - C++
в чем проблема?вроде матрица инициализируется раз выводит первоначальную матрицу это алгоритм форда-фалкерсона. #include &lt;iostream&gt; ...

Входные данные. Метод Форда-Фалкерсона - C++
Доброго времени суток! Есть код, который работает и справляется с основной задачей - нахождением максимального потока сети методом...

Алгоритм Форда - C++
Здравствуйте, помогите пожалуйста с задачей. Дан граф. Каждой дуге приписано некоторое число (вес) cij.Найти все кратчайшие пути между...

Алгоритм Форда-Белмана - C++
Найти расстояние от фиксированной вершины до всех остальных вершин графа. Для задания любая матрица 5*5. Программа на языке С++.

Алгоритм Форда-Беллмана - C++
Доброго времени суток. Есть кривой код: #include &lt;iostream&gt; #include &lt;vector&gt; using namespace std; const int inf = 1555; struct...

Алгоритм Форда-Беллмана - C++
Народ если есть у кого нибудь исходник выложите пожалуйста очень надо. А то везде одно и то же... И ничего не понятно толком=)

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

Алгоритм Форда - Беллмана - C++
Помогите пожалуйста понять что не так у меня. ограничение времени на тест: 1 сек. ограничение памяти на тест: 32768 KB. ввод:...

Восстановление пути из алгоритма Форда-Беллмана - C++
Реализовал алгоритм Форда-Беллмана, но не получается правильно восстановить пути, подскажите, где ошибаюсь. #define...

Матрица Форда Беллмана и метод Дейкстра - 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 =...


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

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

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