Phân loại cạnh cây khung

Buổi 20 — Cây khung nhỏ nhất
Points
32
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho đồ thị vô hướng liên thông gồm $N$ đỉnh và $M$ cạnh có trọng số. Mỗi cạnh có thể thuộc:

  1. Mọi cây khung nhỏ nhất (ALL).
  2. Một số (nhưng không phải tất cả) cây khung nhỏ nhất (SOME).
  3. Không cây khung nhỏ nhất nào (NONE).

Hãy đếm số lượng cạnh thuộc từng loại.

Dữ liệu vào
  • Dòng đầu tiên 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_i, v_i, w_i$ ($1 \le u_i, v_i \le N, 1 \le w_i \le 10^9$).
Dữ liệu ra
  • In ra ba số nguyên cách nhau bởi dấu cách lần lượt là số cạnh thuộc loại ALL, SOME và NONE.
Ví dụ
Input Output
4 5
1 2 1
2 3 1
1 3 1
3 4 2
2 4 3
1 3 1
4 4
1 2 1
2 3 2
3 4 3
1 4 4
3 0 1
Giới hạn
  • $1 \le N \le 10^5$
  • $N - 1 \le M \le 2 \cdot 10^5$
  • $1 \le w_i \le 10^9$
Draft saved