💻
Elearning
CodePath
Problems
Contests
Roadmap
🐱 Scratch
🔐 Login
Rừng Khung Nhỏ Nhất
MST02
## Đề bài Một đồ thị vô hướng có `n` đỉnh và `m` cạnh, không nhất thiết liên thông. Với mỗi thành phần liên thông, hãy chọn một cây khung nhỏ nhất. Hợp của các cây đó gọi là rừng khung nhỏ nhất. Hãy in số thành phần liên thông của đồ thị và tổng trọng số của rừng khung nhỏ nhất. Cạnh âm, cạnh trùng và cạnh khuyên đều có thể xuất hiện. ## Dữ liệu vào - Dòng đầu chứa `n`, `m`. - `m` dòng tiếp theo chứa `u`, `v`, `w`. ## Dữ liệu ra In hai số: số thành phần liên thông và tổng trọng số của rừng khung nhỏ nhất. ## Ràng buộc - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 400000` - `-10^9 ≤ w ≤ 10^9` ## Subtask - Subtask 1 (20%): `n ≤ 9`, `m ≤ 20`. - Subtask 2 (30%): `n ≤ 3000`, `m ≤ 15000`. - Subtask 3 (50%): không có ràng buộc thêm. ## Ví dụ ```text 5 5 1 2 -2 2 3 4 1 3 1 4 5 7 4 4 -10 ``` ```text 2 6 ``` ## Giải thích ví dụ Thành phần `{1,2,3}` có cây nhỏ nhất trọng số `-1`; thành phần `{4,5}` có trọng số `7`. Tổng là `6`.
✅ Đã AC: 1 / 1 submissions
⬅ Contest
🚀 Nộp bài
💡 Gợi ý AI
📌 Bài kế
📋 Copy đề
⚙️
⬅ Contest
🚀 Nộp bài
💡 Gợi ý
📌 Bài kế
📋 Copy
📖 Hướng dẫn học tập
Học trò tri ân
☕ Một ly cà phê sẻ chia
Bạn bè ủng hộ
🍜 Một bát phở ấm lòng
💳 Quét mã ủng hộ tuỳ tâm nhé!
💬 Liên hệ Zalo!
Đóng