Розбір для 1964: THE ROOOOOK
Памʼятайте, що цей розбір слід використовувати лише коли ви застрягли, і не копіювати код з нього. Будь ласка, поважайте автора задачі та автора розбору.
Надсилання офіційного розвʼязку до того, як ви самі розвʼяжете задачу, є порушенням, за яке можна отримати блокування.
Надсилання офіційного розвʼязку до того, як ви самі розвʼяжете задачу, є порушенням, за яке можна отримати блокування.
В цій задачі скористаємося максимальним паросполученням.
Вершини в першій долі будуть позначати вертикалі, а в другій — горизонталі.
ROOKs будуть позначати ребра. ROOK, що розміщена в позиції ~(x_i, y_i)~, з'єднує ребром вершину ~x_i~ першої долі та ~y_i~ другої долі.
Оскільки в максимальному паросполученні одна вершина не може бути з'єднана з більше ніж одним ребром, на кожній вертикалі або горизонталі буде не більше однієї ROOK.
Варто зауважити, що в цій задачі хорошим рішенням є використати деякі оптимізації стосовно алгоритму куна:
Запускати пошук з половини, де є менше вершин.
Перед запуском основного алгоритму розставити деякі ребра жадно, а потім покращити рішення алгоритмом, це прискорить роботу алгоритму.
Коментарі