Добрый день) Решая ГП Европы, придумал задачу В (там где надо сориентировать ребра так, чтобы граф стал Эйлеровым), но написать уже не успевал) Потом прочитал на СФ разбор Ильи Корнакова и тихо порадовался, что знаю как решать такие задачи. Однако на пути из Питера решил написать ее в поезде и получил ВА 5. Искал баг и ничего не нашел, так и не знаю, где косяк. Вот и подумал, может кто подскажет. По шагам то, что я делаю.
1) Ищу минимальный возможный вес ребра и максимально возможный, где минимальный - это максимум из минимумов весов по каждому ребру, а максимальный - максимум всех весов.
2) Бин поиском подбираю вес
3) Строю граф по ребрам у которых вес >= текущему
4) Проверяю граф на достижимость из вершины 0.
5) Для каждой вершины читаю ее полустепень входа и выхода, потом беру минимум из этих двух величин и вычитаю из каждой этот минимум (то есть свожу одну из них в ноль)
6) Добавляю ребра из истока в каждую вершину с положительной полустепенью входа с пропускной способностью, равной этой степени, и в сток добавляю ребра из вершин с положительной полустепенью выхода, с пропускной способностью, равной этой степени.Остальные ребра добавляю в сеть такие как есть с пропускной способностью 1
7) Нахожу макс поток
8) Перебираю ребра в сети, которые не ведут из истока и в сток. Если поток по ребру положительный, то ориентирую это ребро в сторону потока.
9) Строю граф на неориентированных ребрах
10) Проверяю степень каждой вершины этого графа на четность
11) Нахожу для каждой компоненты связности Эйлеров цикл и ориентирую ребра вдоль него.
12) Строю исходный граф с найденной ориентацией ребер и нахожу Эйлеров цикл.
Может где то в логике косяк? В коде не нахожу.