Cây khung nhỏ nhất (HEAP)

View as PDF

Submit solution


Points: 0.08 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem source:
Ðược add lên bởi Vo Khanh Trung
Problem type
Allowed languages
C, C++, Java, Pascal, Python, TEXT

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

Comments

Please read the guidelines before commenting.



  • -5
    HMDuc  commented on 22, Nov, 2021, 20:48

    This comment is hidden due to too much negative feedback. Click here to view it.


  • 7
    I_love_Hoang_Yen  commented on 11, Sep, 2021, 21:34

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