Кубики (решение с использование графов)

Привет, сегодня поговорим про кубики решение с использование графов , обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое кубики решение с использование графов , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

Задание

Родители подарили Пете набор детских кубиков. Поскольку Петя скоро пойдет в школу, они купили ему кубики с буквами. На каждой из шести граней каждого кубика написана буква.

Теперь Петя хочет похвастаться перед старшей сестрой, что научился читать. Для этого он хочет сложить из кубиков ее имя. Но это оказалось довольно сложно сделать — ведь разные буквы могут находиться на одном и том же кубике, и тогда Петя не сможет использовать обе буквы в слове. Правда, одна и та же буква может встречаться на разных кубиках. Помогите Пете!

Дан набор кубиков и имя сестры. Выясните, можно ли выложить ее имя с помощью этих кубиков, и если да, то в каком порядке следует выложить кубики.

Ввод

В первой строке входного файла находится число N(1 <=N<= 100) — количество кубиков в наборе у Пети. Во второй строке записано имя Петиной сестры — слово, состоящее только из больших латинских букв, не длиннее 100 символов. Следующие N строк содержат по 6 букв (только большие латинские буквы), которые написаны на соответствующем кубике.

Вывод

В первой строке выходного файла выведите YES, если выложить имя Петиной сестры данными кубиками можно, и N0 — в противном случае.

Если ответ YES, то во второй строке выведите М различных чисел из диапазона l..N, где М — количество букв в имени Петиной сестры, i-e число должно быть номером кубика, который следует положить на i-e место при составлении имени Петиной сестры. Об этом говорит сайт https://intellect.icu . Кубики нумеруются с 1, в том порядке, в котором они заданы во входном файле. Если решений несколько, выведите любое. Разделяйте числа пробелами.

Пример ввода          Пример вывода 
4                     N0 
ANN 
ANNNNN 
BCDEFG 
HIJKLM 
NOPQRS 

5                     YES 
HELEN                 2 1 3 5 4 
ABCDEF 
GHIJKL 
MNOPQL 
STUVWN 
EIUOZK 

Решение     [вверх]

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

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

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

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

Чтобы получить ответ на вопрос, поставленный в задаче («Выясните, можно ли выложить ее имя с помощью этих кубиков и если да, то в каком порядке следует выложить кубики»), после построения максимального потока по методу Форда-Фалкерсона на заданном графе следует высчитать максимальный исходящий поток Мах. Если значение Мах не равно длине имени Name, то ответ отрицательный (N0), иначе — положительный (YES). Для того чтобы вывести номера использованных кубиков в порядке, обеспечивающем построение имени, нужно для каждой буквы имени найти такую вершину k в графе (и вывести ее номер), что поток от вершины к букве равен 1.

Формальное описание     [вверх]

Cubes()
1. Считать входные данные задачи из файла.
2. Создать двудольный граф, в котором вершины - кубики и буквы английского
   алфавита. Связать кубики с буквами, которые присутствуют на кубике.
2. Создать вершину-исток и соединить ее с вершинами графа, которые
   отвечают кубикам. Пропускная способность для этих  ребер равна единице.
3. Создать вершину-сток и соединить ее с вершинами-буквами, которые 
   присутствуют в имени сестры. Пропускная способность - количество
   повторений буквы в имени.
4. Найти максимальный поток по алгоритму Форда-Фалкерсона 
   между истоком и стоком.
5. Если количество кубиков меньше, чем длина имени или если поток из
   истока не равен длине имени, то считать, что имя сложить невозможно, 
   иначе найти последовательность кубиков. 

На этом все! Теперь вы знаете все про кубики решение с использование графов , Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое кубики решение с использование графов и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов