Vé miễn phí
View as PDF
Submit solution
Points:
100.00 (partial)
Time limit:
1.0s
Memory limit:
1G
Input:
stdin
Output:
stdout
Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text
Vùng liên thông trong đồ thị là tập hợp các đỉnh mà từ một đỉnh bất kỳ có đường đi trực tiếp hoặc gián tiếp đến các đỉnh khác trong tập hợp đó. Cho đồ thị vô hướng có ~N~ đỉnh, ~M~ cạnh. Các đỉnh được đánh số từ ~1~ tới ~N~. Chi phí thăm đỉnh thứ ~i~ là ~t_i~. Bạn có một vé miễn phí để dùng một lần khi thăm ~1~ đỉnh.
Bạn ghé thăm các đỉnh trong vùng liên thông có nhiều đỉnh nhất và sử dụng vé miễn phí để tổng chi phí nhỏ nhất.
*Dữ liệu vào: *
- Dòng 1: Ghi số nguyên dương ~N~, ~M~ ~(M, N ≤ 3000)~.
- Dòng 2: Ghi ~N~ số nguyên dương ~t_i~ là chi phí thăm đỉnh ~i~ (~t_i~ ≤ ~10^9~).
- ~M~ dòng tiếp theo, mỗi dòng ghi số nguyên dương ~u~ và ~v~ thể hiện có đường đi giữa hai đỉnh ~u~ và ~v~ ~(u, v ≤ N)~.
Kết quả: Ghi ra số đỉnh được thăm nhiều nhất và tổng chi phí nhỏ nhất tìm được.
Ví dụ:
INPUT
12 7
1 2 3 1 2 4 4 4 3 3 2 1
1 2
2 5
2 6
6 10
3 4
9 11
9 12
OUTPUT
5 8
(Chọn vùng nhiều đỉnh nhất: 1, 2, 5, 6, 10; Chi phí 1 + 2 + 2 + 4 + 3 = 12. Dùng vé miễn phí cho đỉnh 6, thu được tổng chi phí: 12-4=8)
Comments
iloveamelia