Đáp án Tin 10 - Bài 1 - Olympic 30-4-2013

Bài 1: Cáp quang (Đề thi Tin học 10 – Olympic 30/4/2013)

Công ty viễn thông muốn thu gọn hệ thống mạng cáp quang của mình. Biết rằng hệ thống mạng hiện tại của công ty gồm n nút mạng, giữa hai nút mạng bất kỳ đều có đường kết nối trực tiếp hoặc gián tiếp nhau. Bạn hãy giúp công ty chọn phương án thu gọn sao cho giữa hai nút mạng bất kỳ vẫn có đường kết nối trực tiếp hoặc gián tiếp với nhau mà tổng chiều dài cáp quang toàn mạng còn lại là ít nhất.

Dữ liệu vào: cho trong NODE.INP:

-          Dòng đầu ghi số nguyên dương N (N ≤ 1000);

-          Những dòng tiếp theo, mỗi dòng chứa 3 số nguyên u,v và d, cho biết hai nút u và v có kết nối trực tiếp bằng cáp quang chiều dài d.

Kết quả: ghi ra NODE.OUT số nguyên S là tổng chiều dài cáp quang ít nhất giữ lại cho cả hệ thống.

NODE.INP	NODE.OUT
5 1 2 1 1 3 4 1 4 20 2 3 15 2 4 3 3 5 3 3 4 1 3 5 3 4 5 2	7

ĐÁP ÁN - HƯỚNG DẪN GIẢI

Đây là dạng bài đồ thị cơ bản, áp dụng thuật toán cây bao trùm tối thiểu. Bài toán có thể áp dụng thuật toán như Prim hoặc Kruskal, cả hai thuật toán này rất thông dụng, có cả mã nguồn C và Pascal.