|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
29.05.2014, 22:35 | #1 |
Новичок
Джуниор
Регистрация: 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; } |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Расшифруйте код)) | 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 |