Lát cắt nhỏ nhất của mạng nhỏ
Muốn biết mạng yếu ở đâu, người ta tìm một nhóm ống rẻ nhất mà khi bịt lại thì hàng không
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
Muốn biết mạng yếu ở đâu, người ta tìm một nhóm ống rẻ nhất mà khi bịt lại thì hàng không thể đi từ nguồn tới đích nữa. Đó là lát cắt nhỏ nhất: tập cạnh cần xóa với tổng sức chứa nhỏ nhất để s không còn tới được t.
Yêu cầu
Cho một mạng có hướng gồm n nút, m cạnh có hướng với sức chứa nguyên dương, nguồn s và đích t. Hãy tìm và in ra tổng sức chứa nhỏ nhất của một tập cạnh mà khi xóa hết tập đó thì không còn đường đi nào từ s tới t. Nếu ngay từ đầu s đã không tới được t thì đáp án là 0.
Với m <= 6, hãy thử hết các tập con cạnh (có 2^m tập) và chọn tập rẻ nhất làm mất liên thông; không cần dùng thuật toán luồng.
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 <= 6, 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).
Output
Một số nguyên duy nhất: tổng sức chứa nhỏ nhất của một lát cắ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.
- Tập cạnh bị xóa có thể rỗng nếu s vốn không tới được t.
- Thời gian cho mỗi bộ dữ liệu là 1 giây.
Ví dụ 1
Input
3 2 1 3
1 2 5
2 3 4
Output
4
Ví dụ 2
Input
4 2 1 4
1 2 3
3 4 2
Output
0
Giải thích
Dữ liệu vào:
Bịt riêng cạnh 2 -> 4 (mất 3) thì vẫn còn đường 1 -> 3 -> 4; bịt riêng 1 -> 2 thì vẫn còn 1 -> 3 -> 4. Bịt hai cạnh 1 -> 2 và 1 -> 3 mất 5, còn bịt 2 -> 4 và 3 -> 4 cũng mất 5. Không tập nào rẻ hơn, nên đáp án là 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.
