💻
Elearning
CodePath
Problems
Contests
Roadmap
🐱 Scratch
🔐 Login
Mạng Cáp Tối Thiểu
MST01
## Đề bài Có `n` trạm được đánh số từ `1` đến `n` và `m` phương án nối cáp hai chiều. Phương án thứ `i` nối hai trạm `u_i`, `v_i` với chi phí `w_i`. Hãy chọn một số phương án sao cho mọi trạm liên lạc được với nhau và tổng chi phí nhỏ nhất. Giữa hai trạm có thể có nhiều phương án khác nhau; dữ liệu cũng có thể chứa cạnh khuyên. ## Dữ liệu vào - Dòng đầu chứa `n`, `m`. - `m` dòng tiếp theo, mỗi dòng chứa `u`, `v`, `w`. ## Dữ liệu ra In tổng chi phí của cây khung nhỏ nhất. Nếu không thể nối tất cả trạm, in `-1`. ## Ràng buộc - `2 ≤ n ≤ 200000` - `1 ≤ m ≤ 400000` - `1 ≤ u,v ≤ n` - `-10^9 ≤ w ≤ 10^9` ## Subtask - Subtask 1 (20%): `n ≤ 8`, `m ≤ 20`. - Subtask 2 (30%): `n ≤ 2000`, `m ≤ 10000`. - Subtask 3 (50%): không có ràng buộc thêm. ## Ví dụ ```text 4 5 1 2 3 2 3 2 3 4 4 1 4 10 1 3 5 ``` ```text 9 ``` ## Giải thích ví dụ Chọn các cạnh có chi phí `3`, `2`, `4`; tổng bằng `9`.
✅ Đã AC: 3 / 6 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