Блог пользователя NotImplemented

Автор NotImplemented, 13 лет назад, По-русски
Timus 1811. Дан взвешенный орграф. |V| = 104, |E| = 105, веса произвольные. Найти такой вес ребра w, что в подграфе, образованном из ребер с весами <= w, существует мн-во S, состоящее не более чем из двух вершин, таких, что для ∀ вершины v существует ребро (s, v), где s ∈ S. 

Наблюдение:
Понятно, что для одной из вершин ∈ S, число исходящих ребер >= N/2. Таких вершин не может быть более чем E/2V. Используя его получим сложность: O(E/2V*V*V) = O(E*V), что не проходит по времени.

Спасибо!
  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится
Хм.. Интересная задача!
13 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

а нет, не так. Всего ребер 10^5. Можно сделать события: ребро закончилось, то есть посортим ребра по убыванию. Будем поддерживать количество исходящих ребер из вершины, чтобы уметь вычислять на текущем шаге количество вершин в графе. Так же потребуется set чтобы находить вершину с максимальной степенью. Если эта степень = количеству вершин - 1, то круто. Осталось разобраться со случаем, когда в ответ входят две вершины, для этого можно сохранить куда-нибудь вершины, которые обновились при последнем изменение стоимости ребра w. Далее надо бы пройтись по этому списку и найти две вершины, у которых одинаковое множество вершин, с которыми они связаны, либо уметь поддерживать какое-то ребро из дополнения графа. Пока не придумал как, но поддерживать множество соседних вершин можно хешами, правда, не уверен, что коллизий не будет.

13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Используя только твое наблюдение можно решить задачу (proof: http://acm.timus.ru/status.aspx?space=1&num=1811&author=67320)
нужно только немного ускорить его деревом отрезков:
зафиксируем одну из вершин со степенью >= N/2, таких вершин мало, а именно не больше 2E/V (!). Построим на базе этой вершины дерево отрезков, которое будет отвечать на запрос: какая максимальная цена смс с l-го по r-ый оператор, если на какой то из этих операторов послать смс невозможно, то цена = бесконечности.
теперь будем втупую переберать вторую вершину из S.
если из этой вершины есть ребро к оператору с номером x, а следующее ребро к оператору с номером y, то вместо того чтобы пробегаться по всем операторам из отрезка [x+1, y-1] и узнавать максимальную стоймость отправки сообщения от первой вершины, просто спросим тоже самое у дерева отрезков. Так как вершин с большой степенью мало, то мы будем очень часто спрашивать максимум на больших отрезках и сильно выигрывать по времени.
Осталось только пробежаться по всем вершинам большой степени и сказать ответ)

ЗЫ: в первом сабмите был баг, приводящий к бесконечному циклу.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Вот тут еще должны быть про неё идеи

http://codeforces.me/blog/entry/1187