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

View as PDF
Submit solution
Points: 0.08 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
Ðược add lên bởi Vo Khanh Trung
Problem type
Allowed languages
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

Comments

Please read the guidelines before commenting.


  • -34
    trytoheckgg  commented on Jan. 13, 2022, 11:26 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -77
    HMDuc  commented on Nov. 22, 2021, 1:48 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -32
      nictysine1  commented on April 13, 2022, 3:36 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


    • -33
      ksomg  commented on Jan. 6, 2022, 3:19 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • 33
    I_love_Hoang_Yen  commented on Sept. 11, 2021, 2:34 p.m.

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