Phá bỏ tất cả chu trình với chi phí nhỏ nhất
Points
78
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 và $M$ cạnh. Mỗi cạnh $i$ nối $u_i, v_i$ và có chi phí xóa là $w_i \ge 0$. Hãy tìm tổng chi phí nhỏ nhất để xóa đi một số cạnh sao cho đồ thị còn lại không còn chu trình nào (tức là trở thành một rừng).
Dữ liệu vào
- Dòng đầu 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$, $0 \le w_i \le 10^9$).
Dữ liệu ra
- Một số nguyên duy nhất là tổng chi phí xóa nhỏ nhất.
Ví dụ
| Input | Output |
|---|---|
| 4 5 1 2 4 2 3 5 3 1 2 3 4 6 2 4 3 |
5 |
| 3 2 1 2 10 2 3 20 |
0 |
Giới hạn
- $1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$
- $0 \le w_i \le 10^9$
Community Discussion