Cây khung cân bằng trọng số
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho đồ thị vô hướng liên thông gồm $N$ đỉnh và $M$ cạnh có trọng số. Hãy tìm một cây khung của đồ thị sao cho hiệu giữa trọng số cạnh lớn nhất và trọng số cạnh nhỏ nhất trong cây khung là nhỏ nhất có thể.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N, M$ ($2 \le N \le 100, N-1 \le M \le 1000$).
- $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$ ($1 \le u, v \le N, 1 \le w \le 10^9$).
Dữ liệu ra
- Một số nguyên duy nhất là độ chênh lệch nhỏ nhất có thể.
Ví dụ
| Input | Output |
|---|---|
| 4 5 1 2 1 2 3 4 3 4 7 1 4 5 2 4 6 |
2 |
Giới hạn
- $2 \le N \le 100, N-1 \le M \le 1000$
Community Discussion