На этом шаге рассмотрим формальную постановку задачи о максимальном потоке.
В примерах, рассмотренных на предыдуших шагах, граф задавался матрицей весов своих дуг. Для формальной записи алгоритма удобно, кроме матрицы весов c[i,j], оперировать также списками дуг графа из каждой вершины, которые представлены в следующем виде:
- ka[i] — количество дуг из вершины i;
- a[i,j] — номер вершины, в которую ведет j-я дуга из вершины i.
Например, для графа из 6 вершин массивы ka[i] и a[i,j] таковы (рис. 1, 2):
Рис.1. Количество дуг из вершины i
Рис.2. Номер вершины, в которую ведет j-я дуга из вершины iПусть задан граф c N + 2 вершинами (вершина 0 — исток, вершина N + 1 — сток и "промежуточные" вершины от 1 до N).
Результат решения задачи о максимальном потоке — это построение такого массива f[i,j] (f[i,j] — поток по дуге из вершины i в вершину j), что сумма f[0,j] (для всех j от 1 до N + 1) (исходящий поток) максимальна.
Понятно, что то же максимальное значение имеет и другая величина — входящий поток — сумма f[i,N+1] (для всех i от 0 до N).
Необходимо также отметить, что при решении задач основная трудность часто заключается именно в формализации задачи и организации ввода исходных данных таким образом, чтобы можно было применять стандартный алгоритм нахождения максимального потока.
На следующем шаге рассмотрим пример олимпиадной задачи.
