Cây khung lớn nhất

Buổi 20 — Cây khung nhỏ nhất
Points
15
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Một công ty truyền thông muốn chọn một tập hợp các đường truyền tạo thành cây khung nối tất cả $N$ trạm phát sóng sao cho tổng băng thông của các đường truyền được chọn là lớn nhất có thể.

Hãy tìm tổng trọng số lớn nhất của cây khung (Maximum Spanning Tree), hoặc in ra -1 nếu đồ thị không liên thông.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N, M$ ($1 \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_i, v_i, w_i$ ($1 \le u_i, v_i \le N, -10^9 \le w_i \le 10^9$).
Dữ liệu ra
  • In ra tổng trọng số lớn nhất của cây khung, hoặc -1 nếu đồ thị không liên thông.
Ví dụ
Input Output
4 5
1 2 3
2 3 5
3 4 2
1 4 4
1 3 1
12
3 1
1 2 10
-1
Giới hạn
  • $1 \le N \le 10^5$
  • $0 \le M \le 2 \cdot 10^5$
  • $-10^9 \le w_i \le 10^9$
Draft saved