Luồng cực đại chi phí cực tiểu (Min-Cost Max-Flow - MCMF) bằng SPFA
Cho một mạng luồng có hướng gồm N đỉnh (2 ≤ N ≤ 300) và M cạnh (1 ≤ M ≤ 3000). Mỗi cạnh từ u đến v có dung lượng c ≥ 0 và chi phí truyền tải w cho mỗi đơn vị luồng.
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: spfa, edmonds karp, graph representation.
Nội dung đề bài
Mục tiêu kiến thức
- Hiểu bài toán Luồng cực đại chi phí cực tiểu (Min-Cost Max-Flow).
- Cài đặt thuật toán đường tăng luồng ngắn nhất theo trọng số chi phí bằng SPFA (Shortest Path Faster Algorithm).
- Cập nhật chi phí cạnh ngược -cost và luồng thặng dư.
Mô tả bài toán
Cho một mạng luồng có hướng gồm N đỉnh (2 ≤ N ≤ 300) và M cạnh (1 ≤ M ≤ 3000). Mỗi cạnh từ u đến v có dung lượng c ≥ 0 và chi phí truyền tải w cho mỗi đơn vị luồng.
Hãy tìm luồng cực đại từ đỉnh nguồn 1 đến đỉnh đích N, đồng thời tìm tổng chi phí nhỏ nhất để truyền tải được lượng luồng cực đại đó.
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 ≤ 300, 1 ≤ M ≤ 3000).
- M dòng tiếp theo: Mỗi dòng gồm 4 số nguyên u, v, c, w (1 ≤ u, v ≤ N, c ≥ 0, w ≥ 0).
Output
- In ra hai số nguyên trên một dòng cách nhau bởi dấu cách: Luồng cực đại và Tổng chi phí nhỏ nhất.
Ràng buộc
- 2 ≤ N ≤ 300.
- 1 ≤ M ≤ 3000.
- 0 ≤ c ≤ 104.
- 0 ≤ w ≤ 104.
- Thời gian chạy: 1000ms.
- Bộ nhớ tối đa: 256MB.
Ví dụ 1
Input
4 5
1 2 2 1
1 3 1 2
2 3 1 1
2 4 1 3
3 4 2 1Output
3 10Gợ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.