Một công ty viễn thông đang lên kế hoạch mở rộng mạng lưới dịch vụ của mình tại một khu

Câu hỏi số 859458:

Vận dụng

Một công ty viễn thông đang lên kế hoạch mở rộng mạng lưới dịch vụ của mình tại một khu vực gồm sáu thị trấn: A, B, C, D và F. Để cung cấp dịch vụ internet và điện thoại đến từng thị trấn, công ty cần phải kéo cáp ngầm nối các thị trấn với nhau. Mỗi đoạn cáp nối hai thị trấn có một chi phí nhất định, tùy thuộc vào khoảng cách địa lý và điều kiện địa hình. Sơ đồ dưới đây thể hiện các tuyến cáp có thể xây dựng, cùng với chi phí đi kèm (tính bằng nghìn đô la) cho từng tuyến.

Chi phí tối thiểu (nghìn đô la) mà công ty phải bỏ ra để xây dựng hệ thống cáp sao cho tất cả sáu thị trấn đều được kết nối với nhau là:

A. 780

B. 820

C. 760

D. 800

Đáp án đúng là: A

Quảng cáo

Xem lời giải

Câu hỏi:859458

Phương pháp giải

Liệt kê tất cả các đường đi theo trọng số tăng dần và chọn đường không tạo thành chu trình cho đến khi đủ $n - 1$ cạnh.

Giải chi tiết

Liệt kê các đường đi: $(B,D) = 100$, $(B,E) = 120$, $(A,C) = 140$, $(D,F) = 160$, $(D,E) = 180$, $(E,F) = 220$, $(C,D) = 260$, $(A,B) = 300$.

Chọn cạnh nhỏ nhất (B,D) giá 100.

Chọn cạnh tiếp theo (B,E) giá 120.

Chọn cạnh tiếp theo (A,C) giá 140.

Chọn cạnh tiếp theo (D,F) giá 160.

Cạnh (D,E) giá 180 tạo thành chu trình (B-D-E), bỏ qua.

Chọn cạnh tiếp theo (C,D) giá 260 để kết nối nhóm (A,C) với nhóm (B,D,E,F).

Lúc này tất cả 6 đỉnh đã được kết nối với 5 cạnh.

Tổng chi phí là: $100 + 120 + 140 + 160 + 260 = 780$.

Đáp án cần chọn là: A

Group 2K8 ôn Thi ĐGNL & ĐGTD Miễn Phí

Câu hỏi trước Câu tiếp theo

>> 2K8 Chú ý! Lộ Trình Sun 2026 - 3IN1 - 1 lộ trình ôn 3 kì thi (Luyện thi 26+ TN THPT, 90+ ĐGNL HN, 900+ ĐGNL HCM, 70+ ĐGTD - Click xem ngay) tại Tuyensinh247.com.Đầy đủ theo 3 đầu sách, Thầy Cô giáo giỏi, luyện thi theo 3 giai đoạn: Nền tảng lớp 12, Luyện thi chuyên sâu, Luyện đề đủ dạng đáp ứng mọi kì thi.