Вместо предисловия
Привет, Хабр! Недавно потратил кучу времени в попытках решить данную задачку. Алгоритм и реализация в ней оказались несложными, но связь между постановкой вопроса и использованием потоков, на мой взгляд, не очевидная, и я, потратив какое-то время в поисках каких-то объяснений или намеков на решение в гугле, смог найти только следующую статейку с довольно куцым объяснением. Потому пишу данный пост, в надежде на то, что кому-нибудь он поможет.
Если вы где-то еще видели объяснение этой задачки, скидывайте в комментарии - возможно, я плохо искал.
Постановка задачи
Собственно условие
Вася и Сережа играют в следующую игру. В некоторых клетках клетчатого листка Сережа рисует один из символов 'H', 'O', 'N' или 'C', после чего Вася должен провести между некоторыми находящимися в соседних клетках символами линии так, чтобы получилось корректное изображение химической молекулы. К сожалению, Сережа любит рисовать много символов, и Вася не может сразу определить, возможно ли вообще нарисовать линии нужным способом. Помогите ему написать программу, которая даст ответ на этот вопрос.
В этой задаче проведенные между символами химических элементов линии будем считать корректным изображением молекулы, если они удовлетворяют следующим условиям:
каждая линия соединяет символы, нарисованные в соседних (по стороне) клетках,
между каждой парой символов проведено не более одной линии,
от каждого элемента отходит ровно столько линий, какова валентность этого элемента (1 для H, 2 для O, 3 для N, 4 для C),
пустые клетки ни с чем не соединены, и
хотя бы в одной клетке нарисован какой-то символ.
Входные данные
Первая строка входного файла содержит два натуральных числа n и m (1 ≤ n,m ≤ 50) — размеры листочка, на котором рисует Сережа. Далее следуют n строк по m символов в каждой, задающих конфигурацию химических элементов, которую нарисовал Сережа; пустые клетки задаются символом '.'.
Выходные данные
В выходной файл выведите одно слово «Valid», если линии провести требуемым образом можно, и «Invalid», если нельзя.
При чем здесь поток?
Представьте каждый из атомов как источник какого-то потока. В данной статье предположим бочки литражом от 1 до 4 литров (атомы различных валентностей), причем соседние мы можем соединять трубками (связями), которые пропускают либо 1 литр жидкости, либо нисколько. По этим трубкам между бочек может течь любая жидкость - в данной статье нальем воды.
Но как определить, что и куда будет вытекать? Определим для себя сами. Для этого используем следующее замечание: граф, который, согласно условию, представляет собой множество клеток прямоугольника в качестве вершин и множество сторон клеток в качестве ребер, при детальном рассмотрении оказывается двудольным. Почему?
Во-первых, связи могут образовывать только соседние по стороне клетки. Тогда покрасим текущую клетку в Цвет1, а соседние - в Цвет2. На деле для всего прямоугольника достаточно 2х цветов, и он принимает вид шахматной доски. Рассмотрим первый пример с того же сайта, где взяли условие.
Ну вот и поделим наш граф на две группы - левую, состоящую из темных клеток, и правую, состоящую из белых клеток. Между собой они пересекаться не могут, так как находятся по диагонали друг от друга. По-умному, ребра графа будут инцидентны вершинам строго из разных множеств, и никакие две вершины внутри одного множества не будут инцидентны.
Определим, что клетки темного цвета - это наши "бочки", заполненные до краев водой, а белые клетки - абсолютно пустые бочки, и все наши связи направим из полных бочек в пустые, то есть из темных клеток в белые. Просто потому, что нам так удобнее. В такой системе задача Васи - переливать из пустого в порожнее так, чтобы все наполненные бочки полностью опустошить, а изначально пустые бочки - наоборот, наполнить строго до краёв (то есть задействовать в связях все валентности). Если хоть одна бочка полна или пуста не до конца (то есть валентность какого-либо атома не совпадает с количеством связей, в которых он задействован) - задача не решена, если такая ситуация неизбежна - задача нерешаема.
Что же делать? Пытаться по максимуму опустошить все наполненные бочки, переливая по трубкам как можно больше воды, то есть найти её максимальный поток в нашей сети. Если, вылив максимальный поток воды из полных бочек, мы обнаружим, что (1) в них еще осталась вода или (2) какие-то из пустых бочек не наполнены до краев - Васе даже пытаться не стоит придумать, по каким трубкам что переливать.
Решение
От воды к графам
Как же смоделировать сеть этих бочек и трубок, для которой можно посчитать поток? Понятно, что множество наполненных бочек - это исток, из которого поток вытекает, а множество пустых бочек - это сток, в который он втекает. Поэтому поставим одну большую бочку, из которой изначально и будем разливать воду по "темным" бочкам, и еще одну, в которую будем сливать воду из "белых" бочек после переливания.
Чтобы разлить из большой бочки-истока в каждую "темную" бочку воды ровно столько, сколько в нее поместится, необходимо пропускную способность трубки, ведущую в данную бочку, установить равной литражу данной бочки. Аналогично поступаем и со стоками.
А теперь то же в понятиях графов. К двудольному графу, в котором ребра представляют собой связи между соседними клетками, добавим фиктивную вершину-исток и фиктивную вершину-сток. Из вершины стока проведем ребра в каждую вершину левого множества, установив вес ребра равным валентности атома в этой вершине, а из правого множества по тому же принципу в вершину-сток. Между вершинами, играющими роль атомов, проведем все возможные по условию связи.
Получаем слоистую сеть, в которой ребра ориентированы по увеличению длины пути от истока. Подсчитывая максимальный поток, будем использовать, к примеру, алгоритм Форда-Фалкерсона, пытаясь найти увеличивающий путь, пока пути из истока в сток вообще имеются. С практической точки зрения, мы будем пытаться задействовать связи между атомами так, чтобы реализовать все валентности (использовать трубки так, чтобы перелить из бочек как можно больше воды).
Когда максимальный поток будет найден, остается проверить, не осталось ли воды в изначально полных бочках, и все ли пустые бочки теперь заполнены. Если мы полностью опустошили или наполнили бочку объемом V литров, то через трубку, соединяющую её с истоком или стоком, должно пройти ровно V литров воды. С точки зрения графов нужно проверить, нет ли среди инцидентных истоку или стоку ребер ненасыщенных, т.е. таких, чья пропускная способность использована не по максимуму.
Для этого при составлении графа будем суммировать валентности вершин каждого множества. Если обе суммы равны найденному максимальному потоку, значит, все ребра в этих множествах насыщены, и необходимая комбинация связей нашлась. В противном случае расставить связи никак не получится.
Краткий итог
Красим вершины в шахматном порядке.
Создаем граф на n*m + 2 вершины, 2 из которых - фиктивные исток и сток, черные соединяем с истоком, белые - со стоком.
Вес ребер, инцидентных стоку или истоку, устанавливаем равным валентности соответствующих вершин-атомов, для белых и черных вершин отдельно считаем сумму валентностей.
Соединяем соседние по условию вершины-атомы ребрами веса 1, направляя из черных в белые.
Ищем максимальный поток. Если обе суммы валентностей равны максимальному потоку - выводим «
Valid», иначе - «Invalid».
Реализация
В качестве примера приведу свою реализацию решения задачи на С++.
Удачи!
