Я пытался решить проблему C. Острова Регионального конкурса Азии-Сеула в 2019 году C, но я не могу успеть.
https://icpc.baylor.edu/worldfinals/problems/icpc2019.pdf
Я заметил следующее :
- Когда вы рассматриваете набор посещенных в настоящее время островов (которые все «сгруппированы» вместе), следующий остров также должен быть смежным с группой.
- При наличии 2 возможные маршруты (т.е. оба пути a> b и a> c возможны в соответствии с условием 1, не имеет значения, какой путь выбран.
Мне удалось предложить только метод грубой силы, в котором я протестировал все n ^ 2 возможных пар островов для начальной точки, а затем приступил к выталкиванию соседних островов из списка для алгоритма O (n ^ 3). Это было неосуществимо для входных размеров n = 100 000.
Затем я попытался оптимизировать поиск начальных точек, но это тоже не сильно помогло.
Любые точки в правильное направление будет оценено!