Тема: ACM PKU 1944
http://acm.pku.edu.cn/JudgeOnline/problem?id=1944
Кто что порекомендует? Думал о динамике но ничего не придумал (( Помогите плз.
Спасибо.
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » ACM PKU 1944
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
http://acm.pku.edu.cn/JudgeOnline/problem?id=1944
Кто что порекомендует? Думал о динамике но ничего не придумал (( Помогите плз.
Спасибо.
В начале положим ans=N (все ребра присутствуют). Теперь переберем ребро, которое не присутствует (т.е. место где размыкается цикл). Теперь для каждой пары однозначно определено направление по которому мы будем соединять ребра внутри круга, поэтому просто проходим по всем вершинам и если какое-то ребро начинается в данной вершине, прибавляем к счетчику 1, а если заканчивается - отнимаем 1. Если счетчик не 0, то ставим очередное ребро, иначе не ставим. Ну и каждый раз пытаемся улучшить ans. Сложность выходит O(N^2).
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » ACM PKU 1944