Sức chứa nút cổ chai của một đường đi
Khi đã chọn một đường đi trong mạng, lượng hàng lớn nhất có thể đẩy theo đường đó bị chặn
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
Khi đã chọn một đường đi trong mạng, lượng hàng lớn nhất có thể đẩy theo đường đó bị chặn bởi ống hẹp nhất. Con số đó gọi là nút cổ chai của đường đi, và nó là viên gạch đầu tiên để tính luồng cực đại.
Yêu cầu
Cho một mạng có hướng gồm n nút và m cạnh, mỗi cạnh có dạng u v c (ống từ u tới v với sức chứa c). Dữ liệu còn cho một đường đi hợp lệ trong mạng: dòng đầu của phần này là k (số nút trên đường đi, 2 <= k <= 5), dòng sau là k nhãn nút theo thứ tự đi qua. Mọi cặp nút liên tiếp trên đường đi đều có cạnh tương ứng trong mạng (có thể có cạnh khác không nằm trên đường đi).
Hãy in ra sức chứa nhỏ nhất trong các cạnh nằm trên đường đi đó.
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: hai số nguyên n m (2 <= n <= 6, 1 <= m <= 6).
- 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).
- Dòng tiếp theo: số nguyên k (2 <= k <= 5).
- Dòng cuối cùng: k số nguyên là nhãn các nút trên đường đi, theo đúng thứ tự đi qua.
Output
Một số nguyên duy nhất: sức chứa nhỏ nhất trên các cạnh của đường đi.
Ràng buộc
- Mạng là đồ thị có hướng, không có khuyên (không có cạnh u u).
- Đường đi cho sẵn luôn hợp lệ và không lặp nút.
- Chỉ xét các cạnh nằm trên đường đi, không xét các cạnh khác của mạng.
- Thời gian cho mỗi bộ dữ liệu là 1 giây.
Ví dụ 1
Input
3 2
1 2 5
2 3 4
3
1 2 3
Output
4
Ví dụ 2
Input
2 1
1 2 7
2
1 2
Output
7
Giải thích
Dữ liệu vào:
Đường đi là 1 -> 2 -> 3, gồm hai cạnh có sức chứa 5 và 4. Ống hẹp nhất chứa 4 nên nút cổ chai là 4. Kết quả in ra là 4.
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.
