Luồng cực đại trên mạng bằng thuật toán Edmonds-Karp
Hệ thống truyền dẫn dữ liệu huấn luyện của AI Empire Academy gồm N trạm mạng (2 ≤ N ≤ 500) và M đường truyền dẫn một chiều (1 ≤ M ≤ 5000). Mỗi đường truyền từ trạm u đến tr…
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: bfs, graph representation, std queue.
Nội dung đề bài
Mục tiêu kiến thức
- Hiểu khái niệm Mạng luồng (Flow Network), Luồng khả thi và Đồ thị dư thừa (Residual Graph).
- Cài đặt thuật toán Edmonds-Karp: Tìm đường tăng luồng ngắn nhất (ít cạnh nhất) bằng BFS.
- Cập nhật luồng trên cạnh xuôi và hoàn trả luồng trên cạnh ngược: res_cap[u][v] -= flow, res_cap[v][u] += flow.
Mô tả bài toán
Hệ thống truyền dẫn dữ liệu huấn luyện của AI Empire Academy gồm N trạm mạng (2 ≤ N ≤ 500) và M đường truyền dẫn một chiều (1 ≤ M ≤ 5000). Mỗi đường truyền từ trạm u đến trạm v có dung lượng băng thông tối đa C(u, v) ≥ 0.
Cần gửi dữ liệu từ Trạm nguồn S = 1 đến Trạm đích T = N. Hãy tính lưu lượng luồng cực đại (Maximum Flow) có thể truyền đồng thời qua mạng lưới này.
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc
stdinvà in rastdout. Bài này không yêu cầu viết hàm. - Không dùng
coutđể in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vàostdoutvà làm bài sai. - Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
- Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.
Input
- Dòng 1: Gồm 2 số nguyên N và M (2 ≤ N ≤ 500, 1 ≤ M ≤ 5000).
- M dòng tiếp theo: Mỗi dòng gồm 3 số nguyên u, v, c (1 ≤ u, v ≤ N, u ≠ v, 0 ≤ c ≤ 109) đại diện cho đường cáp từ u sang v có dung lượng c. (Nếu có nhiều đường cáp giữa cùng một cặp trạm theo cùng chiều, dung lượng được cộng dồn).
Output
- In ra một số nguyên duy nhất là giá trị luồng cực đại từ trạm 1 đến trạm N.
Ràng buộc
- 2 ≤ N ≤ 500.
- 1 ≤ M ≤ 5000.
- 0 ≤ c ≤ 109.
- Thời gian chạy: 1000ms.
- Bộ nhớ tối đa: 256MB.
Ví dụ 1
Input
4 5
1 2 3
1 3 2
2 3 1
2 4 2
3 4 3Output
5
*Giải thích:*
- Luồng 1 $\to$ 2 $\to$ 4 gửi được 2 đơn vị.
- Luồng 1 $\to$ 2 $\to$ 3 $\to$ 4 gửi được 1 đơn vị.
- Luồng 1 $\to$ 3 $\to$ 4 gửi được 2 đơn vị.
- Tổng luồng cực đại: $2 + 1 + 2 = 5$.Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.