Cầu Trọng Yếu Trong Mạng

Buổi 78 — Bế giảng Graphs
Points
60
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho một đồ thị vô hướng đơn gồm $N$ đỉnh và $M$ cạnh. Cạnh thứ $i$ nối hai đỉnh $u_i, v_i$ và có chi phí bảo trì $w_i$.

Một cạnh được gọi là cầu nếu khi xóa cạnh đó khỏi đồ thị thì số thành phần liên thông của đồ thị tăng lên.

Hãy đếm số lượng cạnh cầu và tính tổng chi phí bảo trì của tất cả các cạnh cầu trong đồ thị.

Dữ liệu vào
  • Dòng đầu tiên gồm 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 gồm ba số nguyên $u_i, v_i, w_i$ ($1 \le u_i, v_i \le N$, $u_i \neq v_i$, $1 \le w_i \le 10^9$).
Dữ liệu ra
  • Một dòng gồm hai số nguyên: số lượng cạnh cầu và tổng chi phí bảo trì của các cạnh cầu.
Ví dụ
Input Output
5 5
1 2 10
2 3 5
3 1 7
2 4 12
4 5 8
2 20
Giới hạn
  • $1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$
  • $1 \le w_i \le 10^9$
Draft saved