Cây Khung Nhỏ Nhất

View as PDF

Submit solution

Points: 200.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, 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

Dữ liệu

  • Dòng 1: Chứa hai số n,m (1n10000; 1m15000)
  • 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ứ ic trọng số của cạnh đó (1u,vn;0c10000).

Kết quả

Gồm 1 dòng duy nhất: Ghi tổng trọng số của cây khung nhỏ nhất

Input

Copy
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

Output

Copy
5

Comments

Please read the guidelines before commenting.


There are no comments at the moment.