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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 29, средняя оценка - 4.66
Mysterion777
 Аватар для Mysterion777
-74 / 48 / 2
Регистрация: 11.01.2013
Сообщений: 199
29.05.2013, 12:06     алгоритм Форда-Фалкерсона #1
Есть алгоритм Форда Фалкерсона, не пойму как восстановить сам поток пот точкам или ребрам чтобы отобразить его графически, не могу сообразить как.
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++
Алгоритм Форда - Беллмана C++
Помогите алгоритм для char переделать в алгоритм для float C++
C++ Алгоритм Форда-Белмана
C++ Матрица Форда Беллмана и метод Дейкстра
Входные данные. Метод Форда-Фалкерсона C++
C++ Алгоритм Форда-Беллмана

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

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

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