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), что не проходит по времени.
Спасибо!
а нет, не так. Всего ребер 10^5. Можно сделать события: ребро закончилось, то есть посортим ребра по убыванию. Будем поддерживать количество исходящих ребер из вершины, чтобы уметь вычислять на текущем шаге количество вершин в графе. Так же потребуется set чтобы находить вершину с максимальной степенью. Если эта степень = количеству вершин - 1, то круто. Осталось разобраться со случаем, когда в ответ входят две вершины, для этого можно сохранить куда-нибудь вершины, которые обновились при последнем изменение стоимости ребра w. Далее надо бы пройтись по этому списку и найти две вершины, у которых одинаковое множество вершин, с которыми они связаны, либо уметь поддерживать какое-то ребро из дополнения графа. Пока не придумал как, но поддерживать множество соседних вершин можно хешами, правда, не уверен, что коллизий не будет.
Вот тут еще должны быть про неё идеи
http://codeforces.com/blog/entry/1187