Bài toán yêu cầu tìm cách xây dựng hệ thống đường bộ nối tất cả các hòn đảo với tổng chiều dài ngắn nhất. Đây chính là bài toán tìm cây khung nhỏ nhất (Minimum Spanning Tree - MST) trên đồ thị vô hướng có trọng số. Đầu vào gồm số đỉnh V và số cạnh E, tiếp theo là E dòng mô tả các cạnh với định dạng: đỉnh đầu, đỉnh cuối, trọng số. Đầu ra là tổng trọng số của cây khung nhỏ nhất.

Bài toán này có thể giải quyết bằng hai thuật toán phổ biến: Prim và Kruskal. Cả hai đều đảm bảo tìm ra kết quả tối ưu.

1. Thuật toán Prim

Prim tiếp cận từ góc nhìn của các đỉnh. Thuật toán sử dụng chiến lược tham lam: luôn chọn đỉnh gần nhất với cây khung hiện tại để thêm vào. Quy trình gồm ba bước lặp lại:

1. Chọn đỉnh: Tìm đỉnh chưa thuộc cây khung và có khoảng cách nhỏ nhất đến cây hiện tại.
2. Thêm vào cây: Đưa đỉnh vừa chọn vào cây khung.
3. Cập nhật khoảng cách: Xét các đỉnh chưa thuộc cây, cập nhật khoảng cách tối thiểu từ chúng đến cây dựa trên cạnh nối với đỉnh mới (nếu nhỏ hơn giá trị hiện tại trong mảng minDist).

Dưới đây là mã nguồn triển khai bằng JavaScript với readline:

function prim(totalVertices, edgeList) {
  const INF = 10001;
  const grid = Array.from({ length: totalVertices + 1 }, () =>
    new Array(totalVertices + 1).fill(INF)
  );
  const minDist = new Array(totalVertices + 1).fill(INF);
  const inTree = new Array(totalVertices + 1).fill(false);

  for (const [u, v, w] of edgeList) {
    grid[u][v] = w;
    grid[v][u] = w;
  }

  for (let i = 1; i < totalVertices; i++) {
    let chosen = -1;
    let closest = Number.MAX_SAFE_INTEGER;

    for (let j = 1; j <= totalVertices; j++) {
      if (!inTree[j] && minDist[j] < closest) {
        closest = minDist[j];
        chosen = j;
      }
    }

    inTree[chosen] = true;

    for (let j = 1; j <= totalVertices; j++) {
      if (!inTree[j] && grid[chosen][j] < minDist[j]) {
        minDist[j] = grid[chosen][j];
      }
    }
  }

  const totalWeight = minDist
    .slice(2)
    .reduce((acc, val) => acc + val, 0);
  console.log(totalWeight);
}

async function main() {
  const rl = require('readline').createInterface({
    input: process.stdin,
  });
  const iter = rl[Symbol.asyncIterator]();
  const readline = async () => (await iter.next()).value;

  const [v, e] = (await readline()).split(' ').map(Number);
  const edges = [];
  for (let i = 0; i < e; i++) {
    edges.push((await readline()).split(' ').map(Number));
  }
  prim(v, edges);
}

main();

2. Thuật toán Kruskal

Trong khi Prim tập trung vào các đỉnh, Kruskal lại dựa trên các cạnh. Nó phù hợp hơn với đồ thị thưa (ít cạnh). Các bước thực hiện như sau:

1. Sắp xếp cạnh: Tất cả các cạnh được sắp xếp tăng dần theo trọng số.
2. Duyệt cạnh đã sắp xếp: Xét từng cạnh, nếu hai đầu mút của nó không cùng thuộc một tập hợp (trong cấu trúc Disjoint Set Union - DSU), ta thêm cạnh đó vào cây khung và hợp nhất hai tập hợp. Nếu chúng đã cùng tập, bỏ qua để tránh tạo thành chu trình.
3. Kết thúc: Khi đã chọn đủ (V-1) cạnh hoặc duyệt hết các cạnh, quá trình dừng lại.

Dưới đây là triển khai Kruskal với DSU:

function kruskal(totalVertices, edgeList) {
  const parent = Array.from({ length: totalVertices + 1 }, (_, idx) => idx);

  function find(x) {
    if (parent[x] !== x) {
      parent[x] = find(parent[x]);
    }
    return parent[x];
  }

  function union(x, y) {
    const rootX = find(x);
    const rootY = find(y);
    if (rootX !== rootY) {
      parent[rootX] = rootY;
    }
  }

  edgeList.sort((a, b) => a[2] - b[2]);
  let result = 0;

  for (const [u, v, w] of edgeList) {
    if (find(u) !== find(v)) {
      result += w;
      union(u, v);
    }
  }
  console.log(result);
}

async function main() {
  const rl = require('readline').createInterface({
    input: process.stdin,
  });
  const iter = rl[Symbol.asyncIterator]();
  const readline = async () => (await iter.next()).value;

  const [v, e] = (await readline()).split(' ').map(Number);
  const edges = [];
  for (let i = 0; i < e; i++) {
    edges.push((await readline()).split(' ').map(Number));
  }
  kruskal(v, edges);
}

main();

Ví dụ với đầu vào mẫu (7 đỉnh, 11 cạnh), cả hai thuật toán đều cho kết quả là 6, đúng với yêu cầu của bài toán. Cả Prim và Kruskal đều là những giải pháp chuẩn mực cho bài toán tìm cây khung nhỏ nhất, tùy vào tính chất của đồ thị (dày hay thưa) để lựa chọn cho phù hợp.