Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

HSPANTREE - Cây khung nhỏ nhất

Cho đồ thị vô hướng liên thông, có trọng số G = (V, E, w) có n đỉnh, m cạnh, cạnh (u, v) có trọng số w(u, v) và hai đỉnh s, t. Hãy tìm cây khung nhỏ nhất (cây khung có tổng trọng số trên các cạnh nhỏ nhất) của đồ thị G.

Dữ liệu vào:

  • Dòng đầu chứa hai số nguyên n và m là số đỉnh và số cạnh của G.
  • m dòng tiếp theo, mỗi dòng chứa ba số số u, v, c cho biết một cạnh nối hai đỉnh u và v trong G và trọng số c = w(u, v) tương ứng.

Dữ liệu ra:

  • Dòng đầu ghi một số nguyên là tổng trọng số của cây khung.
  • n – 1 dòng tiếp theo, mỗi dòng ghi ba số u v c mô tả một cạnh của cây khung và trọng số của cạnh đó.

Ví dụ:

Dữ liệu vào:
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

Dữ liệu ra:
5
2 1 1
3 1 1
4 2 1
5 2 1
6 3 1

Giới hạn: 1 ≤ n ≤ 5000; n – 1 ≤ m ≤ 106 ; 1 ≤ c ≤ 10000. 


Được gửi lên bởi:noname00.pas
Ngày:2017-10-29
Thời gian chạy:0.100s-1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C-CLANG C CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 JAVA PAS-FPC PYTHON PYTHON3
Nguồn bài:Bài tập thực hành CSL

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.