trang chủ / đề bài / bn_tst_26_c

Sửa chữa mạng

Đề bài

Mô tả

Thời gian vừa qua, mưa bão lũ quét và sạt lở đã làm hư hỏng, đứt rất nhiều tuyến cáp quang nối giữa các trạm thu phát sóng trong thành phố.

Theo khảo sát, có n trạm (được đánh số từ 1 đến n) và m tuyến cáp (được đánh số thứ tự từ 1 đến m) hư hỏng nặng cần phải sửa chữa gấp. Chi phí để sửa chữa tuyến cáp thứ i nối giữa trạm ui và trạm vi là wi.

Chính quyền thành phố hiện có hai phương án ưu tiên sửa chữa độc lập, cả hai đều nhắm đến mục tiêu tối ưu hóa tổng chi phí:

  • Dự án loại 1: Sửa chữa một số tuyến cáp sao cho k trạm trọng điểm i1,i2,…,ik liên lạc được với nhau (tức là có liên lạc giữa bất kỳ trạm iu và iv nào thuộc nhóm này).
  • Dự án loại 2: Sửa chữa một số tuyến cáp sao cho n−k trạm dân sự còn lại (các trạm không nằm trong danh sách trạm trọng điểm ở trên) có thể liên lạc được với nhau.

Yêu cầu: Viết chương trình tính toán tổng chi phí tối thiểu để hoàn thành loại dự án được yêu cầu.

Dữ liệu vào

  • Dòng đầu ghi 4 số n,k,m,t, trong đó n (n≤100) là tổng số trạm thu phát sóng, k là số lượng trạm trọng điểm, m (m≤1000) là số tuyến cáp quang, t=1 là dự án loại 1 hoặc t=2 là dự án loại 2.
  • Dòng tiếp theo ghi k số nguyên dương i1,i2,…,ik (các số đôi một khác nhau).
  • m dòng tiếp theo, dòng thứ i chứa ba số nguyên ui,vi,wi thể hiện có tuyến cáp nối giữa trạm ui và trạm vi với chi phí sửa chữa là wi (1≤wi≤106).

Dữ liệu đảm bảo luôn có đáp án.

Dữ liệu ra

Một số nguyên duy nhất là tổng chi phí tối thiểu để thực hiện dự án được yêu cầu.

Ràng buộc

  • 1≤n≤100, 1≤k≤n, 1≤m≤1000, t∈{1,2}.
  • 1≤ui,vi≤n, ui≠vi, 1≤wi≤106.

Subtasks

  • Subtask 1 (30% số điểm): t=1; k=n.
  • Subtask 2 (30% số điểm): t=1; k=2.
  • Subtask 3 (20% số điểm): t=1; 2<k≤10.
  • Subtask 4 (20% số điểm): t=2; 2<k≤10.

Ví dụ

Input Output Giải thích
5 3 5 1
1 2 3
1 2 1
1 3 1
1 5 1
2 4 2
4 1 5
2 Dự án loại 1 với các trạm trọng điểm 1,2,3: sửa hai tuyến 1−2 và 1−3, tổng chi phí 2.
5 3 5 2
1 2 3
1 2 1
1 3 1
1 5 1
2 4 2
4 1 5
4 Dự án loại 2: cần nối hai trạm dân sự 4 và 5. Đi qua các trạm trọng điểm 2 và 1: 4−2−1−5 có chi phí 2+1+1=4, rẻ hơn tuyến 4−1−5 (chi phí 6).

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0