Thêm Một Đường Dây Xóa Nhiều Cầu Nhất
Points
65
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Một mạng lưới truyền tải liên thông gồm $N$ trạm (đánh số từ $1$ đến $N$) và $M$ đường dây hai chiều (có thể có đường dây song song). Đường dây thứ $i$ nối trạm $u_i$ với $v_i$ và có chi phí rủi ro $w_i > 0$ nếu nó là cầu của đồ thị.
Ban quản lý được phép đầu tư lắp đặt thêm tối đa một đường dây mới nối hai trạm bất kỳ $x, y$ trong mạng. Khi lắp thêm đường dây này, mọi đường dây cầu cũ nằm trên chu trình mới tạo ra sẽ không còn là cầu nữa.
Hãy tìm tổng chi phí rủi ro nhỏ nhất của các đường dây cầu còn lại sau khi lắp thêm tối ưu một đường dây mới.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $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$, $u_i \ne v_i$, $1 \le w_i \le 10^9$).
Dữ liệu ra
In ra một số nguyên duy nhất là tổng chi phí rủi ro nhỏ nhất còn lại của các cầu.
Ví dụ
| Input | Output |
|---|---|
| 6 6 1 2 4 2 3 5 3 4 3 4 5 7 4 6 2 1 2 10 |
2 |
Giới hạn
Thời gian: 1.0s, Bộ nhớ: 256MB.
Community Discussion