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

Входные данные. Метод Форда-Фалкерсона - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Возврат ссылки http://www.cyberforum.ru/cpp-beginners/thread1145965.html
int & function(int); Понятно для чего передают аргументы в функцию как указатели или ссылки.Но зачем функция возвращает ссылку? Чтобы сэкономить память и время?
C++ Сортировка списка Дан список сел и расстояния до них от города. Нужно вывести села в порядке удаленности от города. Городов до 10^8. Расстояния - целые числа, <= 10^6 http://www.cyberforum.ru/cpp-beginners/thread1145958.html
C++ Unsigned char to vector
{ vector<byte> resBuffer; unsigned char buffer; //string reply; //Receive a reply from the server if( recv(sock , buffer , sizeof(buffer) , 0) < 0) { puts("recv failed"); }
Тип BOOL C++
Что API функции возвращают в качестве TRUE? 1? Или любой не 0?
C++ Время затраченное на выполнение любой операции http://www.cyberforum.ru/cpp-beginners/thread1145907.html
Доброго времени суток. Подскажите пожалуйста как мне получить время затраченное на вычисление, например на выполнение цикла?
C++ Как изменить мантиссу double? Привет! Как изменить мантиссу числа типа double? Есть в c++ какая-нибудь встроенная функция? подробнее

Показать сообщение отдельно
Gupi
37 / 2 / 1
Регистрация: 05.06.2011
Сообщений: 36
12.04.2014, 08:19     Входные данные. Метод Форда-Фалкерсона
Доброго времени суток!

Есть код, который работает и справляется с основной задачей - нахождением максимального потока сети методом Форда-Фалкерсона.
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
#include <iostream>
#include <conio.h>
#include <memory.h>
#include <stdio.h>
using namespace std;
const int max_vershin = 40 ;// максимльное кол-во вершин
 
int number_vershin; // число вершин в графе
const int inf = 10000; // некоторое, условное число обозначающее бесконечность
 
 
//Возьмем  g это будет, массив содержащий текушее значение потока, т.е. g[i][j] это будет поток текущий от вершины i к j
int g[max_vershin][max_vershin];
// А массив k будет содержать вместимости ребер, другими словами k[i][j] будет содержать максимальную величину потока способную течь по ребру (i,j)
int k[max_vershin][max_vershin];
 
//Затем заводим  набор вспомогательных переменных используемых функцией FindPath для обхода в ширину
// переменная fw, это значение потока чарез данную вершину, на данном шаге поиска
int fw[max_vershin];
// link используется для нахождения собственно пути
// link[i] хранит номер предыдущей вешины на пути i к истоку
int link[max_vershin]; 
int course[max_vershin]; //кладем все в очередь
int cb, ct; //Для очереди, заводим вспомогательные переменные cb,ct, где cb - указатель начала очереди и ct - число эл-тов в очереди
 
 
// поск пути по которому возможно пустить поток алгоритмом обхода графа в ширину
// функция будет искать путь из истока в сток по которому еще можно пустить поток,
// считая вместимость ребера (i,j) равной k[i][j] - g[i][j],
// т.е. после каждой итерации(одна итерация - один поиcк пути) уменьшаем вместимости ребер,на величину пущеного потока
int FindPath(int head, int end) // head - исток, end - сток
{
        cb = 0; ct = 1; course[0] = head;
        link[end] = -1; // ставим особую метку для стока
        int i;
        int course_begin; //Вершина
        memset(fw, 0, sizeof(int)*number_vershin); // в начале из всех вершин, кроме истока, течет 0
        fw[head] = inf; // а из истока может вытечь сколько угодно
        while (link[end] == -1 && cb < ct)
        {
                // смотрим какие вершины могут быть достигнуты из начала очереди
                course_begin = course[cb];
                for (i=0; i<number_vershin; i++)
                // проверяем можем ли мы пустить поток по ребру (course_begin,i):
                if ((k[course_begin][i] - g[course_begin][i])>0 && fw[i] == 0) 
                {
                        // если можем, то добавляем i в конец очереди
                        course[ct] = i; ct++;
                        link[i] = course_begin; // указываем, что в i добрались из course_begin
                        // и находим значение потока текущее через вершину i
                        if (k[course_begin][i]-g[course_begin][i] < fw[course_begin])
                             fw[i] = k[course_begin][i];
                        else
                             fw[i] = fw[course_begin];
                }
            cb++;// прерходим к следующей в очереди вершине
        }
        // закончили поиск пути
        if (link[end] == -1) return 0; // мы или не находим путь и выходим
        // или находим:
        // тогда fw[end] будет равен потоку который дотек по данному пути из истока в сток
        // тогда изменяем значения массива g для  данного пути на величину fw[end]
        course_begin = end;
        while (course_begin != head) // путь из стока в исток мы восстанавливаем с помощбю массива link
        {
                g[link[course_begin]][course_begin] +=fw[end];
                course_begin = link[course_begin];
        }
        return fw[end]; // Возвращаем значение потока которое мы еще смогли пустить по графу
}
 
// основная функция поиска максимального потока
int max_fw(int head, int end) // head - исток, end - сток
{
        // инициализируем переменные:
        memset(g, 0, sizeof(int)*max_vershin*max_vershin); // по графу ничего не течет
        int max_fw = 0; // начальное значение потока
        int add_fw;//добавить в поток
        do
        {
                // каждую итерацию ищем какй-либо простой путь из истока в сток
                // и какой еще поток мажет быть пущен по этому пути
                add_fw = FindPath(head, end);
                max_fw += add_fw;
        } while (add_fw >0);// повторяем цикл пока поток увеличивается
        return max_fw;
}
 
int main()
{
   int head, end;
   scanf("%d", &number_vershin);
   scanf("%d %d", &head, &end);
   int i, j;
   for (i=0; i<number_vershin; i++)
      for (j=0; j<number_vershin; j++)
         scanf("%d",&k[i][j]);
 
   printf("%d", max_fw(head, end));
   
  
   _getch();
  
 
}
Основная проблема в том, что я не могу понять что вводится в входных данных.

Например:

6 - это количество вершин.
0 5 - я не могу разобраться, что это за строка и что она показывает.
0 16 0 0 13 0
0 0 12 0 6 0
0 0 0 0 9 20
0 0 7 0 0 4
0 0 0 14 0 0
0 0 0 0 0 0 - Это матрица инцидентности или смежности.
Результат: 23. - макс. поток сети.
Помогите разобраться пожалуйста.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 12:52. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru