Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 29.05.2014, 22:35   #1
London1
Новичок
Джуниор
 
Регистрация: 03.04.2014
Сообщений: 2
По умолчанию Расшифруйте пожалуйста...

Есть код программы. Программа вычисляет максимальный поток по алгоритму Форда-Фалкерсона . В программе есть цикл, педагог спрашивает, каким образом программа выходит из этого цикла. И почему addFlow всегда равняется единичке. Заранее спасибо.
#include <memory.h>
#include <stdio.h>
const int MAX_VERTICES = 40;

int NUM_VERTICES; // число вершин в графе
const int INFINITY = 10000; // условное число, обозначающее бесконечность

int f[MAX_VERTICES][MAX_VERTICES]; // f[i][j] - поток, текущий от вершины i к j
int c[MAX_VERTICES][MAX_VERTICES]; // c[i][j] - максимальная величина потока, способная течь по ребру (i,j)

// набор вспомогательных переменных, используемых функцией FindPath - обхода в ширину
int Flow[MAX_VERTICES]; // Flow - значение потока через данную вершину на данном шаге поиска
int Link[MAX_VERTICES]; // Link[i] хранит номер предыдущей вешины на пути i -> исток
int Queue[MAX_VERTICES]; // очередь
int QP, QC; // QP - указатель начала очереди и QC - число эл-тов в очереди

// поиск пути, по которому возможно пустить поток алгоритмом обхода графа в ширину
// функция ищет путь из истока в сток, по которому еще можно пустить поток,
// считая вместимость ребера (i,j) равной c[i][j] - f[i][j]

int FindPath(int source, int target) // source - исток, target - сток
{
QP = 0; QC = 1; Queue[0] = source;
Link[target] = -1;
int i;
int CurVertex;
memset(Flow, 0, sizeof(int)*NUM_VERTICES);
Flow[source] = INFINITY;
while (Link[target] == -1 && QP < QC)
{
CurVertex = Queue[QP];
for (i=0; i<NUM_VERTICES; i++)
if ((c[CurVertex][i] - f[CurVertex][i])>0 && Flow[i] == 0)
{
Queue[QC] = i; QC++;
Link[i] = CurVertex;
if (c[CurVertex][i]-f[CurVertex][i] < Flow[CurVertex])
Flow[i] = c[CurVertex][i];
else
Flow[i] = Flow[CurVertex];
}
QP++;

}

if (Link[target] == -1) return 0;
CurVertex = target;
while (CurVertex != source)
{
f[Link[CurVertex]][CurVertex] +=Flow[target];
CurVertex = Link[CurVertex];
}
return Flow[target];
}

// основная функция поиска максимального потока
int MaxFlow(int source, int target) // source - исток, target - сток
{
memset(f, 0, sizeof(int)*MAX_VERTICES*MAX_VERTIC ES);
int MaxFlow = 0;
int AddFlow;
do
{
AddFlow = FindPath(source, target);
MaxFlow += AddFlow;
} while (AddFlow >0);
return MaxFlow;
}

int main()
{
int source, target;
scanf("%d", &NUM_VERTICES);
scanf("%d %d", &source, &target);
int i, j;
for (i=0; i<NUM_VERTICES; i++)
for (j=0; j<NUM_VERTICES; j++)
scanf("%d",&c[i][j]);

printf("%d", MaxFlow(source, target));
return 0;
}
London1 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Расшифруйте код)) V-ampire Assembler - Ассемблер (FASM, MASM, WASM, NASM, GoASM, Gas, RosAsm, HLA) и не рекомендуем TASM 1 03.06.2013 00:30
расшифруйте код программы БД Silent69 БД в Delphi 3 21.05.2012 19:25
Хитрый файлик - расшифруйте. Питер PHP 1 20.05.2012 14:33
Расшифруйте шифр Цезаря Мокрый Помощь студентам 8 22.04.2011 17:24
Расшифруйте задание))) bullvinkle Помощь студентам 3 26.03.2010 19:49