1584_Min_Cost_to_Connect_All_Points

Решение задачи 1584. Min Cost to Connect All Points

Нам дан двумерный массив points[] размера n, где points[i] = [x_i, y_i] - координаты точки на плоскости. Стоимостью соединения двух произвольных точек этого массива предлагается считать манхэттенское расстояние между ними. Равно оно сумме модулей разностей их координат. То есть, расстояние между точками i и j можно вычислить по формуле |x_i - x_j| + |y_i - y_j|.

Нужно найти минимальную суммарную стоимость соединения всех точек points[]. Точки i и j считаются соединенными, если точки i и j принадлежат к одному и тому же множеству соединенных между собой точек. Другими словами, эти точки можно представить как вершины связного неориентированного графа. Как следует из условия, от нас ожидают объединения точек в граф с минимально возможными ребрами, то есть в граф кратчайших путей или минимальное остовное дерево.

Теперь задача сводится к построению этого дерева. Существует несколько популярных алгоритмов для построения минимального остовного дерева. Для решения этой задачи я выбрал алгоритм Краскала, так как для его применения не нужно строить список инцидентности, а достаточно просто отсортированного по весу множества ребер.

Для эффективной реализации алгоритма понадобится структура хранения добавленных в итоговый граф ребер, называемая системой непересекающихся множеств. В моей реализации эта структура называется UnionFind. Принцип ее работы:

• Множество вершин размера n создается как набор древоподобных структур, где каждая вершина является узлом дерева, а узлы, являющиеся детьми общего родителя считаются соединенными между собой так, что из одной вершины есть путь до другой.
• Изначально у каждой вершины свой уникальный родитель.
• После применения к двум вершинам метода Unite(v, u) вершины v и u должны оказаться в одном дереве. Этот метод сначала проверит не являются ли эти вершины уже узлами общего дерева (тогда метод вернет false), и если не являются, то корень дерева одной из вершин (меньшего по размеру) вешается под корень дерева другой вершины (большего по размеру), и оба множества объединяются.
• Метод Find(v) возвращает корень дерева, узлом которого является вершина v.

Имея в распоряжении структуру UnionFind, можно объединять любые вершины множества |V| размера n ребрами, избегая при этом циклов. Ведь при попытке объединить вершины, которые уже были соединены ранее, избыточным ребром наш метод Unite(u, v) вернет false.

Алгоритм Краскала основан на добавлении в итоговый граф из n вершин, минимального количества ребер минимального возможного веса, при котором граф останется связным и не будет содержать в себе циклов. Этот граф и будет минимальным остовным деревом, а сумма весов его ребер будет ответом на задачу.

Для этого создадим все возможные ребра, соединяющие все возможные пары вершин массива points[]. Для удобства будем их хранить в бинарной куче на минимум. Так на вершине кучи всегда будет ребро наименьшего веса. Извлекая ребро из кучи, будем объединять инцидентные ему вершины в предварительно созданном объекте UnionFind размера n. Если добавление ребра вызывает цикл (для его вершин метод Unite вернул false), отбрасываем ребро, извлекаем из кучи следующее. Если ребро можно добавить, прибавляем его вес к ответу. Повторяем эти шаги, пока количество успешно добавленных ребер не станет равно n - 1, то есть минимально возможное количество ребер для объединения всех вершин уже добавлено. Можно возвращать ответ.

Целиком мое решение здесь.