Cây khung cân bằng
Points
28
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho đồ thị vô hướng có trọng số gồm $N$ đỉnh và $M$ cạnh.
Một cây khung của đồ thị là một tập con gồm $N - 1$ cạnh kết nối tất cả $N$ đỉnh lại với nhau. Độ chênh lệch của một cây khung được định nghĩa là 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 đó.
Hãy tìm độ chênh lệch nhỏ nhất có thể của một cây khung trong đồ thị. Nếu đồ thị không liên thông (không có cây khung), in ra -1. (Nếu $N = 1$, độ chênh lệch là 0).
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N, M$ ($1 \le N \le 200$, $0 \le M \le 2000$).
- $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$) mô tả cạnh nối $u$ và $v$ với trọng số $w$.
Dữ liệu ra
- Một số nguyên duy nhất là độ chênh lệch nhỏ nhất, hoặc
-1nếu không tồn tại cây khung.
Ví dụ
| Input | Output |
|---|---|
| 4 5 1 2 3 2 3 5 3 4 6 1 4 9 2 4 4 |
2 |
| 4 2 1 2 5 3 4 10 |
-1 |
Giới hạn
- $1 \le N \le 200$, $0 \le M \le 2000$.
- $1 \le w \le 10^9$.
Community Discussion