Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Luồng cực đại Edmonds-Karp

    Cho mạng có hướng nnn đỉnh, mmm cung; mỗi cung (u,v)(u,v)(u,v) có sức chứa ccc. Tìm giá trị luồng cực đại từ nguồn sss tới đích ttt.

    Nhiều cung cùng hướng giữa một cặp đỉnh được cộng dồn sức chứa.

    • Định dạng đầu vào:

      Dòng đầu: nnn, mmm, sss, ttt. mmm dòng: uuu, vvv, ccc.

    • Ràng buộc đầu vào:

      2≤n≤2002 \le n \le 2002≤n≤200, 0≤m≤20000 \le m \le 20000≤m≤2000, 0≤c≤1060 \le c \le 10^60≤c≤106, s≠ts \ne ts=t.

    • Định dạng đầu ra:

      Một số nguyên: giá trị luồng cực đại.

    Ví dụ:

    Đầu vào:

    4 5 1 4
1 2 3
1 3 2
2 3 1
2 4 2
3 4 4

    Đầu ra:

    5

    Giải thích:

    Luồng tối đa từ 1 tới 4: đẩy 2 qua 1-2-4, 1 qua 1-2-3-4, 2 qua 1-3-4; tổng giới hạn bởi sức chứa rời nguồn = 5.

    Đang tải editor...