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:
Ðược add lên bởi Vo Khanh Trung
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

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



  • -25
    trytoheckgg  đã bình luận lúc 13, Tháng 1, 2022, 11:26

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -63
    HMDuc  đã bình luận lúc 22, Tháng 11, 2021, 13:48

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -28
      nictysine1  đã bình luận lúc 13, Tháng 4, 2022, 3:36

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -30
      ksomg  đã bình luận lúc 6, Tháng 1, 2022, 3:19

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 25
    I_love_Hoang_Yen  đã bình luận lúc 11, Tháng 9, 2021, 14:34

    Input đảm bảo đồ thị liên thông.