trang chủ / đề bài / dhbb26_dx03_10_c

Mạng trọng yếu

Đề bài

Mô tả

Cho đồ thị vô hướng liên thông gồm n đỉnh và m cạnh, các đỉnh được đánh số từ 1 đến n.

Cạnh thứ i nối hai đỉnh ui, vi và có trọng số dương wi.

Có k đỉnh đặc biệt đôi một khác nhau là t1,t2,…,tk.

Hãy chọn ra một tập cạnh sao cho trong đồ thị tạo bởi các cạnh được chọn, mọi đỉnh đặc biệt nằm trong cùng một thành phần liên thông. Tổng trọng số của các cạnh được chọn phải là nhỏ nhất.

Nói cách khác, ta cần tìm trọng số nhỏ nhất của một đồ thị con liên thông chứa toàn bộ k đỉnh đặc biệt.

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên n, m, k (1≤n≤3000; n−1≤m≤12000; 2≤k≤10).
  • Dòng thứ hai chứa k số nguyên phân biệt t1,t2,…,tk.
  • m dòng tiếp theo, mỗi dòng chứa ba số nguyên u, v, w, mô tả một cạnh vô hướng nối u và v có trọng số w (1≤u,v≤n; u≠v; 1≤w≤109).

Các đỉnh đặc biệt đôi một khác nhau. Đồ thị ban đầu liên thông. Có thể tồn tại nhiều cạnh nối cùng một cặp đỉnh.

Dữ liệu ra

In ra một số nguyên duy nhất: tổng trọng số nhỏ nhất của một đồ thị con liên thông chứa tất cả các đỉnh đặc biệt.

Ràng buộc

  • 1≤n≤3000; n−1≤m≤12000; 2≤k≤10;
  • 1≤u,v≤n, u≠v; 1≤w≤109;
  • đồ thị liên thông, có thể có nhiều cạnh nối cùng một cặp đỉnh.

Subtasks

  • Subtask 1 (20% số điểm): m=n−1, đồ thị là cây.
  • Subtask 2 (30% số điểm): n≤200.
  • Subtask 3 (50% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input Output Giải thích
6 7 3
1 4 6
1 2 3
2 3 2
3 4 4
2 5 2
5 6 1
4 6 7
3 6 6
12 Chọn các cạnh (1,2) trọng số 3, (2,3) trọng số 2, (3,4) trọng số 4, (2,5) trọng số 2 và (5,6) trọng số 1. Ba đỉnh đặc biệt 1,4,6 nằm trong cùng một thành phần liên thông, tổng trọng số 3+2+4+2+1=12. Không có phương án nào nhỏ hơn.
4 5 3
1 2 3
1 4 5
2 4 5
3 4 5
1 2 9
2 3 9
15 Ví dụ thêm (không có trong đề gốc). Chọn ba cạnh nối đỉnh 4 (không đặc biệt) với 1,2,3: tổng 15. Dùng hai cạnh trực tiếp (1,2) và (2,3) tốn 18.

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