Задача 11 — Минимальное остовное дерево, манхэттенская метрика
Даны N точек на плоскости. Стоимость соединения двух точек = манхэттенское расстояние |x₁−x₂| + |y₁−y₂|. Найти минимальную суммарную стоимость, чтобы соединить все точки (MST).
Идея. Строим все пары рёбер с манхэттенскими весами, сортируем по весу и жадно берём алгоритмом Крускала: ребро берём, если его концы в разных компонентах (проверка через DSU). Лемма о безопасном ребре гарантирует оптимальность. (Для больших N есть оптимизация на O(N log N) — соединять только с ближайшими в 4 секторах; здесь показан базовый Крускал на всех парах.)