Cây khung nhỏ nhất (HEAP)
Xem dạng PDF
Gửi bài giải
Điểm:
0,08 (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:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho đơn đồ thị vô hướng liên thông ~G~ = (~V~, ~E~) gồm ~n~ đỉnh và ~m~ cạnh, các đỉnh được đánh số từ ~1~ tới ~n~ và các cạnh được đánh số từ ~1~ tới ~m~. Hãy tìm cây khung nhỏ nhất của đồ thị ~G~
Input
Dòng ~1~: Chứa hai số ~n~, ~m~ (~1 \le n \le 10000~; ~1 \le m \le 15000~)
~M~ dòng tiếp theo, dòng thứ ~i~ có dạng ba số nguyên ~u~, ~v~, ~c~. Trong đó (~u~, ~v~) là chỉ số hai đỉnh đầu mút của cạnh thứ ~i~ và ~c~ trọng số của cạnh đó (~1 \le u~, ~v \le~ ~n~; ~0 \le c \le 10000~).
Output
Gồm ~1~ dòng duy nhất: Ghi trọng số cây khung nhỏ nhất
Sample Input
6 9
1 2 1
1 3 1
2 4 1
2 3 2
2 5 1
3 5 1
3 6 1
4 5 2
5 6 2
Sample Output
5
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Input đảm bảo đồ thị liên thông.