Mạng trọng yếu
Đề bài
Mô tả
Cho đồ thị vô hướng liên thông gồm đỉnh và cạnh, các đỉnh được đánh số từ đến .
Cạnh thứ nối hai đỉnh , và có trọng số dương .
Có đỉnh đặc biệt đôi một khác nhau là .
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ộ đỉnh đặc biệt.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên , , .
- Dòng thứ hai chứa số nguyên phân biệt .
- dòng tiếp theo, mỗi dòng chứa ba số nguyên , , , mô tả một cạnh vô hướng nối và có trọng số .
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
- ; ; ;
- , ; ;
- đồ thị liên thông, có thể có nhiều cạnh nối cùng một cặp đỉnh.
Subtasks
- Subtask 1 ( số điểm): , đồ thị là cây.
- Subtask 2 ( số điểm): .
- Subtask 3 ( 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 trọng số , trọng số , trọng số , trọng số và trọng số . Ba đỉnh đặc biệt nằm trong cùng một thành phần liên thông, tổng trọng số . 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 (không đặc biệt) với : tổng . Dùng hai cạnh trực tiếp và tốn . |
Bình luận