Những cây cầu thiết yếu

Buổi 24 — Mock Contest Phase 1
Points
65
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho đồ thị vô hướng liên thông có trọng số gồm $N$ đỉnh đánh số từ $1$ đến $N$ và $M$ cạnh.

Một cạnh được gọi là thiết yếu nếu nó xuất hiện trong mọi cây khung nhỏ nhất (MST) của đồ thị.

Hãy tính tổng trọng số của tất cả các cạnh thiết yếu trong đồ thị đã cho.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N, M$ ($1 \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, v, w$ ($1 \le u, v \le N$, $1 \le w \le 10^9$) mô tả cạnh nối $u$ và $v$ với trọng số $w$. Đảm bảo đồ thị liên thông.
Dữ liệu ra
  • Một số nguyên duy nhất là tổng trọng số của tất cả các cạnh thiết yếu.
Ví dụ
Input Output
4 5
1 2 1
2 3 1
3 4 2
1 4 2
1 3 1
0
3 3
1 2 5
2 3 5
1 3 5
0
Giới hạn
  • $1 \le N \le 10^5$, $N - 1 \le M \le 2 \cdot 10^5$.
  • $1 \le w \le 10^9$.
Draft saved