Codeforces Educational 3E- Minimum spanning tree for each edge
Xem dạng PDFCho đồ thị chứa ~n~ đỉnh ~m~ cạnh, là đồ thị vô hướng có trọng số với các cạnh không chứa khuyên, ví dụ như cạnh ~(u,u)~ là một khuyên.
Với mỗi cạnh ~(u, v)~, hãy tìm trọng số nhỏ nhất có thể của cây khung chứa cạnh ~(u, v)~. Nói cách khác, ta cần tìm trọng số của cây khung nhỏ nhất chứa cạnh ~(u,v)~.
Trọng số của cây khung là tổng trọng số của tất cả các cạnh có trong cây khung.
Input
Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(1 ≤ n ≤ 2 \times 10^5,~ ~n - 1 ≤ m ≤ 2 \times 10^5)~ - số đỉnh và số cạnh trong đồ thị.
Mỗi dòng trong số ~m~ dòng tiếp theo chứa ba số nguyên ~u_i, v_i, w_i~ ~(1 ≤ u_i, v_i ≤ n, u_i ≠ v_i, 1 ≤ w_i ≤ 10^9)~ - lần lượt là hai đỉnh và trọng số của cạnh thứ ~i~.
Output
In ra ~m~ dòng. Dòng thứ ~i~ chứa trọng số của cây khung nhỏ nhất chứa cạnh thứ i.
Các cạnh được đánh số từ ~1~ đến ~m~ theo thứ tự xuất hiện trong đầu vào.
Sample Input
5 7
1 2 3
1 3 1
1 4 5
2 3 2
2 5 3
3 4 2
4 5 4
Sample Output
9
8
11
8
8
8
9
Bình luận
cảm ơn anh ạ
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Cảm ơn những nổ lực của bạn !
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
lời giải rất hữu ích cảm ơn anh nhiều
Hay quá bạn!