1135. Connecting Cities With Minimum Cost
Есть n городов, пронумерованных от 1 до n. Вам даны целое число n и массив connections, где connections[i] = [xi, yi, costi] указывает, что стоимость соединения города xi и города yi (двунаправленное соединение) равна costi.
Верните минимальную стоимость для соединения всех n городов так, чтобы между каждой парой городов был хотя бы один путь. Если невозможно соединить все n городов, верните -1.
Стоимость - это сумма использованных стоимостей соединений.
Пример:
Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
Output: 6
Explanation: Choosing any 2 edges will connect all cities so we choose the minimum 2.
C# решение
сопоставлено/оригиналpublic class DisjointSet {
private int[] parent;
public DisjointSet(int n) {
parent = new int[n + 1];
for (int i = 0; i <= n; ++i) {
parent[i] = i;
}
}
public int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]);
}
return parent[x];
}
public void Union(int x, int y) {
int rootX = Find(x);
int rootY = Find(y);
if (rootX != rootY) {
parent[rootY] = rootX;
}
}
}
public class Solution {
public int MinimumCost(int n, int[][] connections) {
Array.Sort(connections, (a, b) => a[2].CompareTo(b[2]));
DisjointSet disjointSet = new DisjointSet(n);
int totalCost = 0;
int edgesUsed = 0;
foreach (var connection in connections) {
int x = connection[0];
int y = connection[1];
int cost = connection[2];
if (disjointSet.Find(x) != disjointSet.Find(y)) {
disjointSet.Union(x, y);
totalCost += cost;
edgesUsed++;
if (edgesUsed == n - 1) {
return totalCost;
}
}
}
return edgesUsed == n - 1 ? totalCost : -1;
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class DisjointSet {
private vector<int>& parent;
public DisjointSet(int n) {
parent = new int[n + 1];
for (int i = 0; i <= n; ++i) {
parent[i] = i;
}
}
public int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]);
}
return parent[x];
}
public void Union(int x, int y) {
int rootX = Find(x);
int rootY = Find(y);
if (rootX != rootY) {
parent[rootY] = rootX;
}
}
}
class Solution {
public:
public int MinimumCost(int n, int[][] connections) {
Array.Sort(connections, (a, b) => a[2].CompareTo(b[2]));
DisjointSet disjointSet = new DisjointSet(n);
int totalCost = 0;
int edgesUsed = 0;
foreach (var connection in connections) {
int x = connection[0];
int y = connection[1];
int cost = connection[2];
if (disjointSet.Find(x) != disjointSet.Find(y)) {
disjointSet.Union(x, y);
totalCost += cost;
edgesUsed++;
if (edgesUsed == n - 1) {
return totalCost;
}
}
}
return edgesUsed == n - 1 ? totalCost : -1;
}
}Java решение
сопоставлено/оригиналclass DisjointSet {
private int[] parents;
public void Union(int a, int b) {
int rootA = Find(a);
int rootB = Find(b);
if (rootA == rootB) return;
this.parents[rootB] = rootA;
}
public int Find(int a) {
while (a != this.parents[a]) {
a = this.parents[a];
}
return a;
}
public boolean isInSameGroup(int a, int b) {
return Find(a) == Find(b);
}
public DisjointSet(int N) {
this.parents = new int[N + 1];
for (int i = 1; i <= N; ++i) {
this.parents[i] = i;
}
}
}JavaScript решение
сопоставлено/оригиналclass DisjointSet {
constructor(n) {
this.parent = Array.from({ length: n + 1 }, (_, i) => i);
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]);
}
return this.parent[x];
}
union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX !== rootY) {
this.parent[rootY] = rootX;
}
}
}
var minimumCost = function(n, connections) {
connections.sort((a, b) => a[2] - b[2]);
const disjointSet = new DisjointSet(n);
let totalCost = 0;
let edgesUsed = 0;
for (const [x, y, cost] of connections) {
if (disjointSet.find(x) !== disjointSet.find(y)) {
disjointSet.union(x, y);
totalCost += cost;
edgesUsed++;
if (edgesUsed === n - 1) {
return totalCost;
}
}
}
return edgesUsed === n - 1 ? totalCost : -1;
};Go решение
сопоставлено/оригиналimport "sort"
type DisjointSet struct {
parent []int
}
func NewDisjointSet(n int) *DisjointSet {
parent := make([]int, n+1)
for i := 0; i <= n; i++ {
parent[i] = i
}
return &DisjointSet{parent}
}
func (ds *DisjointSet) Find(x int) int {
if ds.parent[x] != x {
ds.parent[x] = ds.Find(ds.parent[x])
}
return ds.parent[x]
}
func (ds *DisjointSet) Union(x, y int) {
rootX := ds.Find(x)
rootY := ds.Find(y)
if rootX != rootY {
ds.parent[rootY] = rootX
}
}
func minimumCost(n int, connections [][]int) int {
sort.Slice(connections, func(i, j int) bool {
return connections[i][2] < connections[j][2]
})
disjointSet := NewDisjointSet(n)
totalCost := 0
edgesUsed := 0
for _, connection := range connections {
x, y, cost := connection[0], connection[1], connection[2]
if disjointSet.Find(x) != disjointSet.Find(y) {
disjointSet.Union(x, y)
totalCost += cost
edgesUsed++
if edgesUsed == n-1 {
return totalCost
}
}
}
return -1
}Algorithm
Сортировка рёбер:
Отсортируйте все соединения (рёбра) в графе по их весам (стоимости) в порядке возрастания.
Итерация по рёбрам и объединение:
Используйте структуру данных Disjoint Set (Union-Find) для проверки циклов и объединения поддеревьев. Для каждого ребра проверьте, принадлежат ли его концы разным поддеревьям, и если да, объедините их, добавив ребро в минимальное остовное дерево (MST).
Проверка соединённости:
Подсчитайте количество рёбер в MST. Если оно меньше n-1, верните -1, так как соединить все города невозможно. Иначе верните суммарную стоимость рёбер в MST.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.