Luồng cực đại trên mạng rất nhỏ
Mạng ống nước, mạng truyền dữ liệu hay mạng vận tải đều được mô hình hóa thành một đồ thị
Tiến độ của tôi ở bài này
Điểm và code bạn nộp đượ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: cpp-basics, arrays.
Nội dung đề bài
Mô tả bài toán
Mạng ống nước, mạng truyền dữ liệu hay mạng vận tải đều được mô hình hóa thành một đồ thị có hướng: mỗi cạnh là một ống có sức chứa tối đa. Câu hỏi trung tâm của cả chủ đề luồng là: từ nguồn s có thể đẩy tối đa bao nhiêu "hàng" tới đích t mà không vượt sức chứa của bất kỳ ống nào?
Yêu cầu
Cho một mạng có hướng nhỏ gồm n nút (đánh số 1..n), m cạnh có hướng với sức chứa nguyên dương, nguồn s và đích t. Mỗi dòng cạnh có dạng u v c nghĩa là có ống từ u tới v chứa được tối đa c đơn vị hàng.
Hãy tính luồng cực đại từ s tới t. Mạng nhỏ đến mức bạn có thể tìm lần lượt các đường tăng (đường đi từ s tới t chỉ gồm cạnh còn sức chứa) và đẩy thêm hàng trên mỗi đường; một lời giải chỉ cần khoảng hai mươi dòng lệnh.
Quy ước nộp bài
Nộp chương trình solution.cpp đọc dữ liệu từ stdin và in kết quả ra stdout. Chỉ in đúng một số nguyên, không in thêm chữ nào khác.
Input
- Dòng đầu tiên: bốn số nguyên n m s t (2 <= n <= 5, 1 <= m <= 7, 1 <= s, t <= n,
s != t).
- m dòng tiếp theo: mỗi dòng ba số nguyên u v c (1 <= u, v <= n, u != v,
1 <= c <= 50) mô tả một ống có hướng từ u tới v với sức chứa c.
- Mỗi cặp có thứ tự (u, v) xuất hiện nhiều nhất một lần.
Output
Một số nguyên duy nhất: giá trị luồng cực đại từ s tới t.
Ràng buộc
- Mạng là đồ thị có hướng, không có khuyên (không có cạnh u u).
- Mọi sức chứa là số nguyên dương không quá 50.
- Mỗi cặp có thứ tự (u, v) chỉ được nêu một lần.
- Thời gian cho mỗi bộ dữ liệu là 1 giây.
Ví dụ 1
Input
4 4 1 4
1 2 3
1 3 2
2 4 3
3 4 2
Output
5
Ví dụ 2
Input
3 2 1 3
1 2 10
2 3 4
Output
4
Giải thích
Dữ liệu vào:
Đẩy 3 đơn vị theo đường 1 -> 2 -> 4 (đường hẹp nhất là 3), rồi đẩy 2 đơn vị theo đường 1 -> 3 -> 4 (đường hẹp nhất là 2). Sau đó không còn đường tăng nào, nên luồng cực đại là 3 + 2 = 5. Kết quả in ra là 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.
