💻
Elearning
CodePath
Problems
Contests
Roadmap
🐱 Scratch
🔐 Login
Các Tuyến Đường Đã Xây
MST04
## Đề bài Có `n` thành phố. `k` cặp thành phố đã được nối sẵn và có thể đi qua miễn phí. Ngoài ra có `m` tuyến đường có thể xây, tuyến `u-v` tốn `w`. Hãy tìm chi phí nhỏ nhất cần trả thêm để mọi thành phố liên thông. Các cặp nối sẵn có thể dư thừa hoặc lặp lại. ## Dữ liệu vào - Dòng đầu chứa `n`, `m`, `k`. - `k` dòng tiếp theo chứa hai đầu của một kết nối đã có. - `m` dòng sau chứa `u`, `v`, `w`. ## Dữ liệu ra In chi phí nhỏ nhất; in `-1` nếu không thể nối tất cả thành phố. ## Ràng buộc - `2 ≤ n ≤ 200000` - `0 ≤ k,m ≤ 400000` - `0 ≤ w ≤ 10^9` ## Subtask - Subtask 1 (20%): `n ≤ 9`. - Subtask 2 (30%): `n ≤ 3000`. - Subtask 3 (50%): không có ràng buộc thêm. ## Ví dụ ```text 5 5 2 1 2 4 5 2 3 4 3 4 6 1 5 20 2 5 10 1 3 7 ``` ```text 10 ``` ## Giải thích ví dụ Ba nhóm ban đầu là `{1,2}`, `{3}`, `{4,5}`. Xây hai đường chi phí `4` và `6`.
✅ Đã AC: 1 / 2 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