Sức chứa rời nguồn và sức chứa vào đích
Trước khi chạy một thuật toán luồng, người ta thường kiểm tra nhanh xem mạng có "cân" 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
Trước khi chạy một thuật toán luồng, người ta thường kiểm tra nhanh xem mạng có "cân" không: tổng sức chứa của các ống rời khỏi nguồn so với tổng sức chứa của các ống đổ vào đích. Nếu hai con số này lệch nhau thì mạng bị nghẽn ở một phía, và biết sớm sẽ tiết kiệm thời gian suy nghĩ.
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ính A là tổng sức chứa của tất cả các cạnh rời khỏi s (tức các cạnh có dạng s v c) và B là tổng sức chứa của tất cả các cạnh đi vào t (tức các cạnh có dạng u t c). In ra YES nếu A = B, ngược lại in NO.
Chú ý: một cạnh s t c được tính cho cả A lẫn B, còn cạnh nối hai nút khác thì không được tính vào con số nào.
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 YES hoặc NO viết hoa, 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 <= 6, 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).
Output
In ra YES nếu tổng sức chứa rời nguồn bằng tổng sức chứa vào đích, ngược lại in NO.
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.
- Chỉ so sánh hai tổng, không cần quan tâm luồng có tồn tại hay không.
- 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 5
Output
YES
Ví dụ 2
Input
3 2 1 3
1 2 5
2 3 4
Output
NO
Giải thích
Dữ liệu vào:
Cạnh rời nguồn 1 là 1 -> 2 với sức chứa 5, vậy A = 5. Cạnh đi vào đích 3 là 2 -> 3 với sức chứa 5, vậy B = 5. Hai giá trị bằng nhau nên kết quả là YES.
Nếu dòng cuối là 2 3 4 thì B = 4 còn A = 5, kết quả sẽ là NO.
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.
