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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Найти количество чисел, делящихся на 3 и 5 без остатка http://www.cyberforum.ru/cpp-beginners/thread883252.html
Заданная последовательность целых чисел. Найти количество чисел, делящихся на 3 и 5 без остатка. Очень прошу помогите кто знает! Заранее огромное спасибо!
C++ Написать программу, которая удаляет из введенной строки любой введенный символ Написать программу, которая удаляет из введенного рядка любой необходимый введенный с клавиатуры символ. Процесс удаления выделить в отдельную процедуру. Очень прошу помогите кто знает! Заранее огромное спасибо! http://www.cyberforum.ru/cpp-beginners/thread883249.html
Построение конечного недетерминированного автомата C++
Добрый день, помогите пожалуйста разобраться. Где-то в выполнении алгоритма ошибка. Задача: Постройте конечный автомат, допускающий цепочки, которые можно построить соединением без пробелов следующих слов: ОР, ОРДА, ДАР, РА. В случае возможности представления указать, разбить цепочки на данные слова, выставив между ними пробелы. (Указание: воспользоваться в качестве промежуточного этапа...
C++ В матрице М(N, M) найти суму элементов четных строк
В матрице М(N, M) найти суму элементов парных рядов. Очень прошу помогите кто знает! Заранее огромное спасибо!
C++ Выполнить транспонирование заданной матрицы http://www.cyberforum.ru/cpp-beginners/thread883218.html
Разработать алгоритм и программу. Дана матрица B размерностью n x m (2<=n,m<=50 – вводятся пользователем). Элементы матрицы bij являются целыми числами, принимающими значения в диапазоне . Заполнение матрицы осуществляется в соответствии с выбором пользователя: - пользовательский ввод с клавиатуры; - заполнение случайными числами в установленном диапазоне. Выполнить транспонирование данной...
C++ Метод пузырька #include <iostream> #include <stdlib.h> #include <time.h> using namespace std; int main() { srand(time(NULL)); int const size = 100; подробнее

Показать сообщение отдельно
Mysterion777
 Аватар для Mysterion777
-74 / 48 / 2
Регистрация: 11.01.2013
Сообщений: 199
29.05.2013, 12:06     алгоритм Форда-Фалкерсона
Есть алгоритм Форда Фалкерсона, не пойму как восстановить сам поток пот точкам или ребрам чтобы отобразить его графически, не могу сообразить как.
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] ) );
          }
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 07:53. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru