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

Наблюдение:

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

Спасибо!