VOI 20 Bài 6 - Động đất - VNOJ: VNOI Online Judge

VOI 20 Bài 6 - Động đất

Điểm: 1,50 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

Kỳ thi Học sinh giỏi Quốc gia 2020 - Ngày 2

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Đọc đề gốc tại đây.

Đất nước AZ có ~n~ thành phố vừa phải hứng chịu một trận động đất mạnh. Nhiều tòa nhà và các công trình công cộng bị phá hủy, làm tê liệt toàn bộ hệ thống giao thông giữa các thành phố. Sau những nỗ lực của chính phủ, có ~n - 1~ con đường hai chiều nối giữa ~n~ thành phố được sửa chữa để đảm bảo tính liên thông đi lại giữa ~n~ thành phố. Các thành phố được đánh số từ ~1~ đến ~n~. Con đường thứ ~k~ ~(k = 1, 2, \dots, n - 1)~ nối hai thành phố ~i_k~ và ~j_k~ có độ dài ~d(i_k, j_k)~ km. Theo dự báo, trong thời gian tới có thể xảy ra một trận động đất nữa, do đó, chính phủ đang lên kế hoạch ứng phó. Theo thông tin thu nhận được, hiện tại thành phố ~i~ ~(i = 1, 2, \dots, n)~ đang có ~p_i~ nhân viên cứu hộ. Chính phủ muốn điều chỉnh lại số lượng nhân viên cứu hộ ở các thành phố sao cho độ chênh lệch nhân viên cứu hộ giữa các thành phố là nhỏ nhất. Độ chênh lệch nhân viên cứu hộ giữa các thành phố được tính bằng hiệu số nhân viên cứu hộ ở thành phố có nhiều nhân viên nhất với thành phố có ít nhân viên nhất.

Tại mỗi thành phố đều có xe dùng để vận chuyển nhân viên cứu hộ (giả thiết số xe tại mỗi thành phố đủ nhiều để phục vụ vận chuyển), mỗi xe có khả năng vận chuyển không quá ~c~ nhân viên cứu hộ. Nếu muốn vận chuyển ~q~ nhân viên cứu hộ từ thành phố ~i~ sang thành phố ~j~ bằng đường nối trực tiếp thì thành phố ~i~ sẽ cần ~\lceil q/c \rceil~ xe, trong đó ~\lceil x \rceil~ là số nguyên nhỏ nhất không nhỏ hơn ~x~ và độ dài đường đi mà mỗi xe phải đi là ~d(i, j)~. Sau khi đến thành phố ~j~, các nhân viên cứu hộ sẽ ở lại hoặc có thể tiếp tục di chuyển sang thành phố khác bằng xe của thành phố ~j~. Để tiết kiệm chi phí vận chuyển, chính phủ cần xây dựng phương án vận chuyển sao cho tổng độ dài đường đi của các xe dùng để vận chuyển là ngắn nhất mà vẫn thỏa mãn yêu cầu nêu trên.

Yêu cầu: Cho thông tin về ~n -1~ con đường và số nhân viên cứu hộ tại mỗi thành phố. Hãy tìm phương án vận chuyển nhân viên cứu hộ mà tổng độ dài đường đi của các xe dùng vận chuyển là ngắn nhất mà vẫn đảm bảo yêu cầu độ chênh lệch nhân viên cứu hộ giữa các thành phố là nhỏ nhất.

Input

Dòng đầu chứa hai số nguyên dương ~n~ và ~c~ ~(c \leq 10^6)~;
Dòng thứ hai gồm ~n~ số nguyên không âm ~p_1, p_2, \dots, p_n~ ~(p_i \leq 10^6)~;
Dòng thứ ~k~ trong số ~n - 1~ dòng tiếp theo chứa ba số nguyên ~i_k, j_k, d(i_k, j_k)~ thỏa mãn ~1 \leq i_k < j_k \leq n~ và ~0 < d(i_k, j_k) \leq 10^6~.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Dòng đầu chứa một số nguyên là tổng độ dài ngắn nhất của các xe dùng để vận chuyển đảm bảo yêu cầu độ chênh lệch nhân viên cứu hộ giữa các thành phố là nhỏ nhất;
Dòng thứ hai chứa số nguyên ~s~ là số lượng đợt vận chuyển;
Dòng thứ ~h~ trong ~s~ dòng tiếp theo chứa ba số nguyên dương ~i_h, j_h, q_h~, nghĩa là thành phố ~i_h~ sẽ có các xe vận chuyển ~q_h~ nhân viên cứu hộ sang thành phố ~j_h~ (giá trị ~q_h~ phải nhỏ hơn hoặc bằng số lượng nhân viên của thành phố ~i_h~ tại thời điểm vận chuyển).

Giới hạn

Có ~20\%~ số test ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~n = 3~;
~40\%~ số test khác ứng với ~40\%~ số điểm của bài thỏa mãn điều kiện: ~n \leq 3\,000~ và mỗi thành phố có không quá ~2~ đường nối trực tiếp tới thành phố khác;
~40\%~ số test còn lại ứng với ~40\%~ số điểm của bài thỏa mãn điều kiện: ~n \leq 3\,000~.

Đối với mỗi test, nếu thí sinh đưa ra đúng giá trị tổng độ dài ngắn nhất của các xe dùng để vận chuyển, thí sinh sẽ được ~70\%~ số điểm của test đó, nếu tiếp tục đưa ra được một phương án vận chuyển đúng, thí sinh sẽ được ~30\%~ số điểm còn lại.

Sample Input

Sample Output

Note

Giải thích: Cần hai xe vận chuyển ~19~ nhân viên cứu hộ từ thành phố ~3~ về thành phố ~1~ và hai xe vận chuyển ~20~ nhân viên cứu hộ từ thành phố ~4~ về thành phố ~2~, cuối cùng cần một xe vận chuyển ~1~ nhân viên từ thành phố ~1~ sang thành phố ~2~. Độ chênh lệch nhân viên cứu hộ giữa các thành phố bằng ~1~ và tổng độ dài đường đi của các xe là ~2 \times 1 + 2 \times 2 + 1 \times 1 = 7~ (km).

Bình luận

Hãy đọc nội quy trước khi bình luận.

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