Cây khung có cạnh lớn nhất nhỏ nhất
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho đồ thị vô hướng có trọng số gồm $N$ đỉnh ($N \ge 2$) và $M$ cạnh. Hãy tìm một cây khung của đồ thị sao cho trọng số lớn nhất trong các cạnh của cây khung đó là nhỏ nhất có thể (Minimum Bottleneck Spanning Tree). In ra giá trị trọng số lớn nhất đó, hoặc -1 nếu đồ thị không liên thông.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N, M$ ($2 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$).
- $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$, $0 \le w \le 10^9$).
Dữ liệu ra
- Một số nguyên duy nhất là trọng số cạnh lớn nhất nhỏ nhất của cây khung, hoặc
-1.
Ví dụ
| Input | Output |
|---|---|
| 4 5 1 2 10 2 3 5 3 4 8 1 4 20 1 3 7 |
8 |
| 3 1 1 2 4 |
-1 |
Giới hạn
- $2 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$
- $0 \le w \le 10^9$
Community Discussion