На этом шаге рассмотрим конкретную олимпиадную задачу на поиск максимального потока.

    Группа из N (3 ≤ N ≤ 200) мам устраивает новогоднюю вечеринку в детском саду. Каждая мама может приготовить несколько различных видов пищи, измеряемой в единицах, называемых "блюдо". Всего имеется D (5 ≤ D ≤ 100) различных видов пищи. Каждый вид пищи обозначается числом в диапазоне от 1 до D.

    Координатор детской вечеринки хочет максимизировать общее количество блюд, которые будут принесены на вечеринку, но имеет установленный лимит на количество блюд каждого типа.

    Каждая мама может принести K (1 ≤ K ≤ 5) блюд, но они должны отличаться друг от друга. К примеру, одна мама не может принести 3 пирожка с говядиной, но может принести пирожок, булочку и конфету. Каково максимальное количество пищи, которую мамы могут принести на вечеринку?

    Входные данные:

   Строка 1: Три целых числа: N, K, D

   Строка 2: D неотрицательных чисел — предел суммарного количества для каждого из различных блюд, которые могут быть принесены на вечеринку.

   Строки 3.. N + 2: Каждая строка содержит начальное целое Z (1 ≤ Z ≤ D), обозначающее количество типов различных блюд, которое может приготовить одна мама; остаток строки содержит Z целых чисел — идентификаторов типов пищи, которую может приготовить мама, соответствующая текущей строке (в строке 3 — мама1, в строке 4 — мама2, и т. д.).

   Пример ввода [файл party.in]:

4 3 5 (4 мамы, каждая до 3 блюд, всего 5 различных типов пищи)
2 2 2 2 3 (2 блюда типов 1,2,3,4 и 3 блюда типа 5)
4 1 2 3 4 (1-я мама может приготовить 4 различных блюда 1,2,3,4)
4 2 3 4 5 (2-я мама может приготовить 4 различных блюда 2,3,4,5)
3 1 2 4 (3-я мама может приготовить 3 различных блюда 1,2,4)
3 1 2 3 (4-я мама может приготовить 4 различных блюда 1,2,3)

    Выходные данные:

    Одна строка содержит одно целое число — максимальное количество блюд, которое может быть принесено на вечеринку.

    Пример вывода [файл party.out]:

9

    Пояснения:

Мама1 принесет блюда 3 и 4;
Мама2 принесет блюда 3, 4 и 5;
Мама3 принесет блюда 1 и 2;
Мама4 принесет блюда 1 и 2.

    Рассмотрим граф, состоящий из N + D вершин. Вершины с номерами от 1 до N соответствуют мамам вершины с номерами от N + 1 до N + D соответствуют различным видам пищи (блюдам).

    Прежде всего мы должны добавить в граф вершины исток (вершину с номером 0) и сток (вершину с номером Finish = N + D + 1). Понятно, что от истока должны быть дуги ко всем вершинам 1..N (мамам), а от вершин N + l.. N + D (блюда) должны быть дуги к стоку. Каковы же должны быть веса введенных дуг от истока и к стоку?

    Для дуг "от истока&uot;: c[0, i] = К (для всех i от 1 до N), поскольку каждая мама может принести K блюд. Соответствующий фрагмент программы выглядит следующим образом:

ka[0]:=N;  {Из истока - N дуг - к каждой маме} 
for i:=1 to N do 
begin 
    a[0,i]:=i; {Номер вершины, соединенной с истоком} 
    c[0,i]:=K; {ee вес - максимальное кол-во блюд для мамы} 
end;

    Для дуг "к стоку": c[i, Finish] = Lim[i-N] (для всех i от N + 1 до N + D), поскольку имеется лимит на количество блюд каждого типа. Соответствующий фрагмент программы выглядит следующим образом:

for i:=1 to D do read(input,Lim[i]); {Пределы блюд каждого типа} 
{Добавляем вершину-сток} 
for i:=N+1 to N+D do 
begin 
    ka[i]:=1; 
    a[i,1]:=Finish; {одна дуга от каждого блюда к стоку} 
    c[i,Finish]:=Lim[i-N]; {ee вес - предел числа блюд данного типа} 
end;

    Мы строим дугу от мамы i к блюдут в том и только в том случае, если i может приготовить блюдо j. Вес каждой такой дуги должен получить значение 1, поскольку блюда, которые принесет корова, должны отличаться друг от друга. Соответствующий фрагмент программы выглядит следующим образом:

{Добавляем вершины от мам к блюдам}
for i:=1 to N do {Для каждой мамы}
begin 
    read(input,Z); ka[i]:=Z; {Количество блюд, которые она готовит} 
    for j:=1 to Z do {Для каждого такого блюда}
    begin 
      read(input,FoodID); {Читаем его номер}
      a[i,j]:=N+FoodID; {Добавляем дугу от мамы к блюду} 
      c[i,a[i,j]]:=1; {Bec такой дуги - 1} 
    end; 
end; 

    Мы имеем граф, заданный списками дуг {ka[i], a[i,j]} и матрицей весов c[i,j], на котором требуется решить задачу о построении максимального потока f[i,j]. После чего ответ на вопрос, поставленный в задаче ("Каково максимальное количество пищи, которую мамы могут принести на вечеринку?"), можно получить, например, следующим образом:

{Поток, входящий в вершину-сток, с номером Finish}
Max:=0; 
for i:=N+1 to N+D do Max:=Max+f[i,Finish]; 
writeln(output,Max);

    На следующем шаге рассмотрим пример применения метода поиска максимального потока.

Предыдущий шаг Содержание Следующий шаг