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 chi phí cực tiểu

    Cho mạng có hướng gồm nnn đỉnh và mmm cung. Mỗi cung từ uuu tới vvv có dung lượng capcapcap và chi phí đơn vị costcostcost (chi phí cho mỗi đơn vị luồng đi qua). Cho đỉnh nguồn sss và đỉnh đích ttt.

    Hãy tìm luồng cực đại từ sss tới ttt, và trong số mọi luồng cực đại, tìm luồng có tổng chi phí nhỏ nhất.

    Ví dụ: Một cung s→ts\to ts→t với cap=3,cost=2cap=3, cost=2cap=3,cost=2 cho luồng 333 và chi phí 666.

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

      Dòng đầu chứa bốn số nguyên n m s tn\ m\ s\ tn m s t. mmm dòng tiếp theo, mỗi dòng bốn số u v cap costu\ v\ cap\ costu v cap cost.

    • 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, 1≤s,t≤n1 \le s, t \le n1≤s,t≤n, s≠ts \ne ts=t, 0≤cap≤10000 \le cap \le 10000≤cap≤1000, 0≤cost≤10000 \le cost \le 10000≤cost≤1000. Không có cung âm.

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

      In ra hai số nguyên: giá trị luồng cực đại và tổng chi phí nhỏ nhất tương ứng, cách nhau bởi một dấu cách.

    Ví dụ:

    Đầu vào:

    2 1 1 2
1 2 3 2

    Đầu ra:

    3 6

    Giải thích:

    Chỉ có một cung 1->2 dung lượng 3, chi phí đơn vị 2. Luồng cực đại là 3, tổng chi phí là 3*2 = 6.

    Đang tải editor...