Hướng dẫn giải của Cây Khung Nhỏ Nhất

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

Lời giải: Cây Khung Nhỏ Nhất

Hướng tiếp cận

Kruskal cho MST, kết hợp đếm số MST bằng cách liệt kê tập con theo nhóm trọng số.

Nhận xét quan trọng

Thuật toán Kruskal xét cạnh theo trọng số tăng dần, các cạnh cùng trọng số có thể hoán đổi thứ tự.
Mỗi trọng số xuất hiện tối đa 3 lần → mỗi nhóm có tối đa $2^{3} = 8$ tập con cần xét.
Số MST = tích số cách chọn cạnh ở mỗi nhóm trọng số.

Thuật toán

Sắp xếp cạnh theo trọng số, chạy Kruskal tìm tổng MST.
Xử lý từng nhóm cạnh cùng trọng số:
- Xác định số cạnh cần thêm ( $n e e d$ ) và trạng thái đích (DSU sau khi thêm tất cả cạnh khả thi).
- Liệt kê tất cả tập con kích thước $n e e d$ , đếm số tập con tạo ra cùng kết quả kết nối.
Nhân các cách chọn lại (modulo $10^{9} + 7$ ).

Độ phức tạp

Thời gian: $O (M \log M + M \cdot N)$ (mỗi nhóm xử lý $O (8 \cdot N)$ )
Bộ nhớ: $O (N + M)$

Bình luận

Không có bình luận tại thời điểm này.