Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumminimum-spanning-tree

Min Cost to Connect All Points

Problem (yeniden ifade)

Düzlemde noktalar. Kenar maliyeti Manhattan |x1-x2| + |y1-y2|. Tüm noktaları bağlayan MST ağırlığını döndür.

Sezgi

Tam graf, n ≤ 1000, n² kenar olur. Her çifti üret, Kruskal.

Yaklaşımlar

Kruskal, Manhattan

Doğrulanmadı

Zaman O(n² log n)Alan O(n²)

Fikir. i < j için (i, j, manhattan) ekle. Sırala, n-1 kenara kadar birleştir.

Yürüyüş. [[0,0],[2,2],[3,10],[5,2],[7,0]] → 20.

Trade-off. Bir tohumdan Prim, yoğun O(n²) tarama ile tüm kenarları saklamaz; Kruskal şablon ve daha basit. Noktalar 0-indeksli.

Çözüm

export function minCostConnectPoints(points: number[][]): number {
  const n = points.length;
  const edges: [number, number, number][] = [];
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      const w = Math.abs(points[i]![0]! - points[j]![0]!) + Math.abs(points[i]![1]! - points[j]![1]!);
      edges.push([i, j, w]);
    }
  }
  edges.sort((a, b) => a[2] - b[2]);
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x: number): number => (parent[x] === x ? x : (parent[x] = find(parent[x]!)));
  let cost = 0, used = 0;
  for (const [u, v, w] of edges) {
    const a = find(u), b = find(v);
    if (a === b) continue;
    parent[a] = b;
    cost += w;
    used++;
    if (used === n - 1) break;
  }
  return cost;
}

export function minCostConnectPoints(points: number[][]): number {
  const n = points.length;
  const edges: [number, number, number][] = [];
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      const w = Math.abs(points[i]![0]! - points[j]![0]!) + Math.abs(points[i]![1]! - points[j]![1]!);
      edges.push([i, j, w]);
    }
  }
  edges.sort((a, b) => a[2] - b[2]);
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x: number): number => (parent[x] === x ? x : (parent[x] = find(parent[x]!)));
  let cost = 0, used = 0;
  for (const [u, v, w] of edges) {
    const a = find(u), b = find(v);
    if (a === b) continue;
    parent[a] = b;
    cost += w;
    used++;
    if (used === n - 1) break;
  }
  return cost;
}

Şablon bağlantısı

Tam grafı somutlaştırdıktan sonra Kruskal. LC 1135 ile aynı, üretilmiş kenar listesiyle.

Yansıma

Maliyet Manhattan. Tüm çiftler kenar. Kruskal n−1 kenar seçer. Prim aynı toplamı verir.
n = 1 cevap 0. Aynı nokta maliyet 0. Negatif koordinat mutlak değerde sorun değil.
Kenar sayısı n². Sıralama maliyeti belirler. Döngüye düşen kenar atlanır.