Chuyến Xe Gringotts

Ngân hàng Gringotts đang vận chuyển vàng từ kho tổng $S$ về căn hầm $T$ tại Hogwarts. Hệ thống hầm mỏ gồm $N$ trạm (đánh số từ $0$ đến $N-1$) và $M$ tuyến đường xe kéo một chiều.

Các yêu tinh Gringotts cho phép bạn điều phối xe kéo, nhưng sau đó sẽ phá hoại hệ thống để giữ vàng lại ngân hàng.

Thể thức

Giai đoạn 1 - Đề xuất: Bạn nhận $V$ xe kéo và phải phân bổ chúng vào $M$ tuyến đường, thỏa mãn:

• Tổng xe đi ra từ $S$ bằng $V$
• Tại mỗi trạm trung gian $u$ ($u\ne S,u\ne T$): tổng xe vào = tổng xe ra (bảo toàn luồng)
• Số xe trên mỗi tuyến là số nguyên không âm

Giai đoạn 2 - Phá hoại: Yêu tinh chọn tối đa $K$ tuyến đường và phong tỏa hoàn toàn. Chúng sẽ chọn sao cho lượng xe về được $T$ là nhỏ nhất.

Mục tiêu: Phân bổ xe sao cho lượng xe tối đa về được $T$ sau khi bị phá hoại là lớn nhất.

Cài đặt

Bạn cần cài đặt hàm sau:

long long solve(int N, int M, int S, int T, int K, long long V,
                std::vector<int> U, std::vector<int> W);

• $N,M$: số trạm và số tuyến đường
• $S,T$: trạm nguồn và trạm đích
• $K$: số tuyến đường tối đa bị phá
• $V$: tổng số xe kéo
• $U,W$: tuyến đường thứ $i$ đi từ $U[i]$ đến $W[i]$

Trong hàm này, bạn phải gọi đúng một lần:

void assign_carts(std::vector<long long> C);

với $C$ là mảng $M$ phần tử, $C[i]$ là số xe phân bổ cho tuyến đường thứ $i$.

Giá trị trả về của hàm solve không được sử dụng.

Ràng buộc

• $2\le N\le 500$
• $1\le M\le 2000$
• $0\le K\le 3$
• $1\le V\le {10}^{18}$
• Đồ thị có thể có cạnh song song và/hoặc tự vòng
• Luôn tồn tại ít nhất một đường đi từ $S$ đến $T$

Subtasks

Ví dụ