Комментарии 3
Вроде бы, в книжке, которую я читал, для задачи максимального потока дают больше алгоритмов. В частности, там вот такое описано: https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%BF%D1%80%D0%BE%D1%82%D0%B0%D0%BB%D0%BA%D0%B8%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F_%D0%BF%D1%80%D0%B5%D0%B4%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0
провести между некоторыми находящимися в соседних клетках символами линии так, чтобы получилось корректное изображение химической молекулы.
Формулировка задания однозначно подразумевает, что должна получиться ОДНА молекула. Однако решение свободно пропускает многосвязные схемы (простейший вариант - квадрат 2х2 с четырьмя водородами, https://ideone.com/eR9aTm, оба возможных решения которого - две отдельные молекулы).
Вы правы: исходя из формулировки в этой фразе подразумевается ровно одна молекула. В то же время в условии, в расшифровке понятия "корректного изображения молекулы" приведены условия, которые в итоге этого не подразумевают:
каждая линия соединяет символы, нарисованные в соседних (по стороне) клетках,
между каждой парой символов проведено не более одной линии,
от каждого элемента отходит ровно столько линий, какова валентность этого элемента (1 для H, 2 для O, 3 для N, 4 для C),
пустые клетки ни с чем не соединены, и
хотя бы в одной клетке нарисован какой-то символ.
Исходя из них, вариант с несколькими молекулами вполне подходит, да и в тестах ничего ломающего такую логику не попалось. Косяк, скорее, самого условия, но можно в качестве тренировки и с дополнительным условием задачку порешать)
Химия. Максимальный поток