На этом шаге рассмотрим решение задачи "Кубики".

    Составим для данной задачи граф следующим образом: в качестве базовых вершин будем рассматривать заданные кубики, а также вершины, соответствующие буквам, которые могут быть написаны на заданных кубиках 26 заглавных букв латинского алфавита).

    Добавим также вершину-исток (ее соединим со всеми вершинами, соответствующими кубиками) и вершину-сток (с ней соединим все вершины, соответствующие буквам).

    Фрагменты программы, которые обеспечат необходимый ввод исходных данных и построение графа, приведены ниже:

readln (N); {Количество кубиков} 
readln (Name); {Имя Петиной сестры}  
for i := 1  to  N do readln(Qubics[i]); {Надписи на кубиках}  
Finish := N + 26  + 1 ; {Кубики + алфавит + сток} 

    Поскольку с каждого кубика может быть использована только одна буква, то веса дуг от истока к кубикам равны 1.

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

    Фрагмент графа от вершин, соответствующих заглавным буквам латинского алфавита, к стоку определяется именем Петиной сестры (переменная Name), которое по условиям задачи требуется составить из исходных кубиков:

{Добавляем вершину-сток} 
for i := 1 to Length(Name) do 
begin 
   NomLet := Ord(Name[i]) - Ord('A') + 1; 
   ka[N + NomLet] := 1; 
   a[N + NomLet,1] := Finish; {Одна дуга на каждую букву из имени} 
   inc(c[N + NomLet, Finish]); {ee вес - количество таких букв в имени}
end; 

    Поскольку имя Петиной сестры может включать повторяющиеся буквы, то при формировании веса соответствующей дуги используется инкрементирование — inc(c[N + NomLet, Finish]).

    Наконец для каждой буквы на каждом кубике строится дуга от соответствующего кубика к соответствующей букве.

    Заметим, что на одном кубике буквы могут повторяться, и мы можем для таких дуг либо увеличивать их вес, либо добавлять новую дугу (с весом 1 — именно такой вариант и реализован в приведенном фрагменте программы). Алгоритм построения максимального потока работает и в графах, содержащих более одной дуги между одной и той же парой вершин.

{Добавляем дуги от кубиков к буквам} 
for i := 1  to N do {Для каждого кубика}  
begin 
   for j := 1  to 6  do {Для каждой буквы на кубике}  
   begin 
      NomLet := Ord(Qubics[i,j]) - Ord('A') + 1; {Вычисляем номер буквы}  
      a[i,j] := N + NomLet; {Добавляем дугу от кубика к букве}  
      c[i, a[i,j]] := 1; {Bec такой дуги - 1}  
      NomKub[Nomlet] := 1; 
      inc(ka[i]) 
   end;
end; 

    Чтобы получить ответ на вопрос, поставленный в задаче ("Выясните, можно ли выложить ее имя с помощью этих кубиков и если да, то в каком порядке следует выложить кубики"), после построения максимального потока назаданном графе следует высчитать максимальный исходящий поток Мах:

Max := 0; 
for i := N + 1 to N + 26 do Max := Max + f[i, Finish];

    Если значение Мах не равно длине имени Name, то ответ отрицательный (N0), иначе — положительный (YES). Для того чтобы вывести номера использованных кубиков в порядке, обеспечивающем построение имени, нужно для каждой буквы имени (NomLet) найти такую вершину k в графе (и вывести ее номер), что f[k, Nomlet] = 1. Фрагмент программы, выводящий ответ задачи, приводится ниже:

If Max <> Length(Name) then writeln('NO') 
else 
begin 
     writeln('YES'); 
     for i := 1 to Length(Name) do 
     begin 
         NomLet := Ord(Name[i]) - Ord('A') + 1; {Вычисляем номер буквы} 
         for k := 1 to n do 
             if f[k, N + NomLet] = 1 then 
             begin 
		 write(k,' '); 
                 f[k, N + NomLet] := 0; 
                 break; 
             end; 
    end;
end;

    Архив с примером можно взять здесь.

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

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