Chuyến Xe Gringotts

Điểm: 8,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++

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 \neq S, u \neq 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 \leq N \leq 500$
$1 \leq M \leq 2000$
$0 \leq K \leq 3$
$1 \leq V \leq 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

Subtask	Điểm	Ràng buộc
1	15	$K = 0$
2	20	$K = 1$ , $N, M \leq 50$
3	30	Đồ thị là lưới ô vuông $W \times H$
4	35	Không có ràng buộc bổ sung

Ví dụ

Input	Output	Giải thích
$N = 4, M = 4, S = 0, T = 3, K = 1, V = 100$ Tuyến: $(0 \to 1), (0 \to 2), (1 \to 3), (2 \to 3)$	$50$	Nếu `assign_carts({100, 0, 100, 0)}`: yêu tinh phá $(0 \to 1)$ thì 0 xe về được. Nếu `assign_carts({50, 50, 50, 50})`: yêu tinh phá bất kỳ đường nào, vẫn có 50 xe về được. Đây là phương án tối ưu.

Bình luận

Không có bình luận tại thời điểm này.