Cây khung cân bằng

Buổi 24 — Mock Contest Phase 1
Points
28
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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 -1 nế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$.
Draft saved