Hướng dẫn giải của Moo Route (Gold) - Chuyên Tin Online Judge

Hướng dẫn giải của Moo Route (Gold)

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: Moo Route (Gold)

Hướng tiếp cận

Tìm $K$ đường đi không chia sẻ cạnh từ $s$ đến $t$ sử dụng max flow.

Thuật toán

Xây dựng mạng lưới từ đồ thị.
Chạy max flow từ $s$ đến $t$ với dung lượng $K$ .
Trả về tổng chi phí của các luồng.

Độ phức tạp

Thời gian: $O (K \times (N + M) \log 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.