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

Optimize Water Distribution in Village

Problem (yeniden ifade)

n ev. i evine kuyu wells[i-1] maliyet. Çift yönlü borular [house1, house2, cost] suyu paylaşır. Her evin suya kavuşmasının minimum maliyetini döndür.

Sezgi

Kuyu, “sanal rezervuardan boru.” 0 düğümünü ev i’ye wells[i-1] ağırlığıyla bağla, n+1 düğümün MST’sini al. Kruskal kuyu ve borunun en ucuz karışımını seçer.

Yaklaşımlar

Kruskal, sanal kuyu

Doğrulanmadı

Zaman O((n+E) log (n+E))Alan O(n)

Fikir. Kenarlar = kuyu kenarları (0, i, wells[i-1]) artı borular. Sırala, n kenara kadar birleştir (n+1 köşeli ağaç).

Yürüyüş. n=3, wells [1,2,2], pipes [[1,2,1],[2,3,1]]. 1’e kuyu (1) + iki boru (1+1) üç kuyuyu yener. Toplam 3.

Trade-off. Şablon bu id için Prim listeler; sanal düğümlü Kruskal aynı MST. Evler 1-indeksli.

Çözüm

export function minCostToSupplyWater(n: number, wells: number[], pipes: number[][]): number {
  const edges: number[][] = [];
  for (let i = 0; i < n; i++) edges.push([0, i + 1, wells[i]!]);
  for (const p of pipes) edges.push(p);
  edges.sort((a, b) => a[2]! - b[2]!);
  const parent = Array.from({ length: n + 1 }, (_, i) => i);
  const find = (x: number): number => (parent[x] === x ? x : (parent[x] = find(parent[x]!)));
  let cost = 0, used = 0;
  for (const e of edges) {
    const a = find(e[0]!), b = find(e[1]!);
    if (a === b) continue;
    parent[a] = b;
    cost += e[2]!;
    used++;
    if (used === n) return cost;
  }
  return cost;
}

export function minCostToSupplyWater(n: number, wells: number[], pipes: number[][]): number {
  const edges: number[][] = [];
  for (let i = 0; i < n; i++) edges.push([0, i + 1, wells[i]!]);
  for (const p of pipes) edges.push(p);
  edges.sort((a, b) => a[2]! - b[2]!);
  const parent = Array.from({ length: n + 1 }, (_, i) => i);
  const find = (x: number): number => (parent[x] === x ? x : (parent[x] = find(parent[x]!)));
  let cost = 0, used = 0;
  for (const e of edges) {
    const a = find(e[0]!), b = find(e[1]!);
    if (a === b) continue;
    parent[a] = b;
    cost += e[2]!;
    used++;
    if (used === n) return cost;
  }
  return cost;
}

Şablon bağlantısı

Modelleme hilesinden sonra Kruskal. LC 1135 ile aynı UF; ekstra köşe “kuyu kur”u kodlar.

Yansıma

Kuyu, sanal düğüm 0’dan eve bir kenar. Borular gerçek kenar. Kruskal, n+1 düğümlü ağaçta n kenar.
Pahalı kuyu, ucuz boruya yenilir. Her evin kuyusu varsa boru gerekmez.
Tek ev o evin kuyusu. Sanal düğüm her evi bağlar, kopuk bileşen kalmaz.