Cây khung lớn nhất
Points
15
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề 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
-1nế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$
Community Discussion