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();
} |
(
