MST и DSU (25 ноября 2016)

1. Потенциалы
1. Дана система неравенств на n переменных. Каждое неравенство имеет вид x_i - x_j ≤ δ_ij. Неравенств m. Найти решение системы или сказать, что его не существует, за O(nm).
2. Как после применения потенциалов, полученных Форд-Беллманом из вершины s, найти за O(E) кратчайшие пути из s во все вершины?


2. MST
1. Проверить, что минимальное по весу остовное дерево единственно. O(mlogm). Решение Примой. Решение Краскалом.
2. Найти второе по весу остовное дерево.
3. Дан взвешанный граф G. Дано минимальное остовное дерево на нем. Поменяем вес у ребра e. Найдите новое минимальное остовное дерево за O(n + m).
4. Дан орграф, постройте остовное дерево с корнем в вершине 1 минимального веса.


3. DSU
1. Кодим DSU [code]
2. Пусть вес пути − максимальное ребро на пути. Насчитать матрицу расстояний.
3. В каждой клетке прямой записано число 0 или 1. Поступает информация: четность числа единиц на отрезке [L_i,R_i]. Найти первый запрос, после которого данные противоречивы.
4. C помощью DSU в offline посчитать минимумы (максимумы) на нескольких отрезках массива
5. C помощью DSU в offline посчитать минимумы (максимумы) на нескольких вертикальных путях в подвешенном дереве


4. Бонус
1. Даны n произвольных точек на плоскости, построить MST за O(n log n)
2. Доказать, что даже DSU с одной лишь эвристикой сжатия путей работает за O(n log n)