Cây khung nhỏ nhất thứ hai

Buổi 25 — Disjoint Set Union Data-structures Graphs Trees
Points
90
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho đồ thị vô hướng liên thông có trọng số gồm $N$ đỉnh và $M$ cạnh. Hãy tìm trọng số của cây khung nhỏ nhất thứ hai (strictly second-best MST), tức là cây khung có tổng trọng số nhỏ nhất mà lớn hơn hẳn trọng số của cây khung nhỏ nhất (MST). Nếu không tồn tại cây khung nào có tổng trọng số lớn hơn hẳn MST, in ra -1.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N, M$ ($2 \le N \le 10^5, N - 1 \le M \le 2 \cdot 10^5$).
  • $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u_i, v_i, w_i$ ($1 \le u_i, v_i \le N, 1 \le w_i \le 10^9$).
Dữ liệu ra
  • Một số nguyên duy nhất là trọng số của cây khung nhỏ nhất thứ hai, hoặc -1.
Ví dụ
Input Output
4 5
1 2 1
2 3 2
3 4 3
1 3 4
2 4 5
8
Giới hạn
  • $2 \le N \le 10^5, N - 1 \le M \le 2 \cdot 10^5, 1 \le w_i \le 10^9$
Draft saved