Cây khung nhỏ nhất
Submit solution
Points:
3
Time limit:
1.0s
Memory limit:
977M
Author:
Problem types
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG
Cho đơn đồ thị liên thông vô hướng có trọng số trên cạnh 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ị
Input
Dòng đầu chứa hai số n, m \((1 <= n <= 10000; 1 <= m <= 20000)\)
m dòng tiếp theo mỗi dòng chứa ba số nguyên u, v, w. Trong đó (u, v) là chỉ số hai đỉnh đầu mút còn w trọng số của cạnh đó \((1 <= u, v <= n; 1 <= w <= 1000)\)
Output
Ghi ra một số nguyên là trọng số nhỏ nhất của cây khung
Ví dụ
Input
7 11
1 2 4
1 3 1
1 7 3
2 4 6
2 3 2
2 5 1
3 5 8
3 6 3
4 5 5
5 6 2
5 7 3Output
14
Comments