USACO 2019 - Tháng 12 - Hạng Vàng

Gần đây, Nông dân John đã mua một trang trại mới để mở rộng đế chế sản xuất sữa của mình. Trang trại mới được nối với một thị trấn gần đó bằng một mạng lưới đường ống, và FJ muốn tìm ra tập hợp đường ống tốt nhất để mua nhằm bơm sữa từ trang trại đến thị trấn.

Mạng lưới đường ống được mô tả bởi \(N\) điểm nối (các đầu mút của đường ống), được đánh số thuận tiện từ \(1 \ldots N\) (\(2 \leq N \leq 1000\)). Điểm nối 1 biểu thị trang trại của FJ và điểm nối \(N\) là thị trấn. Có \(M\) đường ống hai chiều (\(1 \leq M \leq 1000\)), mỗi đường ống nối một cặp điểm nối. Đường ống thứ \(i\) có giá \(c_i\) đô la để FJ mua sử dụng và có thể hỗ trợ lưu lượng \(f_i\) lít sữa mỗi giây.

FJ chỉ muốn mua các đường ống thuộc một đường đi có hai đầu mút là các điểm nối 1 và \(N\). Chi phí của đường đi là tổng chi phí của các đường ống trên đường đi. Lưu lượng trên đường đi là giá trị nhỏ nhất trong các lưu lượng của những đường ống trên đường đi (vì đây là nút thắt cổ chai đối với dòng chảy dọc đường đi). FJ muốn tối đa hóa lưu lượng của đường đi chia cho chi phí của đường đi. Đề bài đảm bảo tồn tại một đường đi từ \(1\) đến \(N\).

Phân nhóm

• Các test 2–5 thỏa mãn \(N,M \leq 100\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(M\). Mỗi dòng trong \(M\) dòng tiếp theo mô tả một đường ống bằng bốn số nguyên: \(a\) và \(b\) (hai điểm nối khác nhau được đường ống nối lại), \(c\) (chi phí của đường ống) và \(f\) (lưu lượng của đường ống). Chi phí và lưu lượng đều là các số nguyên dương trong phạm vi \(1 \ldots 1000\).

Dữ liệu ra

In \(10^6\) lần giá trị tối ưu, cắt bỏ phần thập phân để thu được một số nguyên (tức là làm tròn xuống số nguyên thấp hơn liền kề nếu giá trị này không phải là số nguyên).

Ví dụ

3 2
2 1 2 4
2 3 5 3

428571

Nguồn

USACO 2019 December Contest, Gold - Milk Pumping: https://usaco.org/index.php?page=viewproblem2&cpid=969

Tác giả: Brian Dean.

Nông dân John dự định xây dựng \(N\) trang trại (\(1 \leq N \leq 10^5\)) được nối với nhau bằng \(N-1\) con đường, tạo thành một cây (tức là mọi trang trại đều có thể đi đến nhau và không có chu trình). Mỗi trang trại có một cô bò với kiểu là một số nguyên \(T_i\) từ \(1\) đến \(N\), kể cả hai đầu mút.

\(M\) người bạn của Nông dân John (\(1 \leq M \leq 10^5\)) thường đến thăm ông. Trong chuyến thăm của người bạn \(i\), Nông dân John sẽ cùng người bạn đi dọc theo đường đi duy nhất từ trang trại \(A_i\) đến trang trại \(B_i\) (có thể xảy ra trường hợp \(A_i=B_i\)). Ngoài ra, họ có thể nếm sữa của bất kỳ cô bò nào dọc theo đường đi. Vì phần lớn bạn bè của Nông dân John cũng là nông dân, họ có sở thích rất khắt khe về sữa. Mỗi người bạn chỉ uống sữa từ một kiểu bò nhất định. Mỗi người bạn của Nông dân John chỉ vui nếu có thể uống loại sữa mình ưa thích trong chuyến thăm.

Hãy xác định liệu mỗi người bạn có vui sau chuyến thăm hay không.

Phân nhóm

• Test 2 là ví dụ thứ hai bên dưới.
• Test 3 thỏa mãn \(N \leq 10^3\), \(M \leq 2\cdot 10^3\).
• Các test 4–7 thỏa mãn \(C_i \leq 10\) (\(C_i\) được định nghĩa bên dưới).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\).

Dòng thứ hai chứa \(N\) số nguyên \(T_1,T_2,\ldots,T_N\), cách nhau bởi dấu cách. Kiểu của cô bò ở trang trại thứ \(i\) được biểu thị bằng \(T_i\).

Mỗi dòng trong \(N-1\) dòng tiếp theo chứa hai số nguyên phân biệt \(X\) và \(Y\) (\(1 \leq X,Y \leq N\)), cho biết có một cạnh giữa trang trại \(X\) và trang trại \(Y\).

\(M\) dòng tiếp theo chứa các số nguyên \(A_i\), \(B_i\) và \(C_i\). \(A_i\) và \(B_i\) biểu thị hai đầu mút của đường đi trong chuyến thăm của người bạn \(i\), còn \(C_i\) (\(1 \leq C_i \leq N\)) cho biết kiểu bò có sữa mà người bạn đó thích uống.

Dữ liệu ra

In một xâu nhị phân độ dài \(M\). Ký tự thứ \(i\) của xâu phải là 1 nếu người bạn thứ \(i\) sẽ vui, hoặc là 0 nếu không.

Ví dụ

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

10110

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

0110

Nguồn

USACO 2019 December Contest, Gold - Milk Visits: https://usaco.org/index.php?page=viewproblem2&cpid=970

Tác giả: Spencer Compton.

Bessie đã chơi trò chơi đối kháng nổi tiếng Moortal Cowmbat từ lâu. Tuy nhiên, gần đây các nhà phát triển trò chơi đã tung ra một bản cập nhật buộc Bessie phải thay đổi phong cách chơi của mình.

Trò chơi sử dụng \(M\) nút được gắn nhãn bằng \(M\) chữ cái thường đầu tiên (\(1 \leq M \leq 26\)). Chuỗi chiêu thức yêu thích của Bessie trong trò chơi là một xâu \(S\) độ dài \(N\) biểu thị các lần nhấn nút (\(1 \leq N \leq 10^5\)). Tuy nhiên, do bản cập nhật gần nhất, giờ đây mọi chuỗi chiêu thức phải được tạo thành từ một loạt "đợt nhấn", trong đó một đợt nhấn được định nghĩa là một dãy gồm cùng một nút được nhấn liên tiếp ít nhất \(K\) lần (\(1 \leq K \leq N\)). Bessie muốn sửa chuỗi chiêu thức yêu thích để tạo ra một chuỗi mới có cùng độ dài \(N\), nhưng được tạo thành từ các đợt nhấn nút nhằm đáp ứng sự thay đổi về luật chơi.

Bessie mất \(a_{ij}\) ngày để luyện cách nhấn nút \(j\) thay cho nút \(i\) tại bất kỳ vị trí cụ thể nào trong chuỗi chiêu thức của mình (tức là chi phí để đổi một chữ cái cụ thể trong \(S\) từ \(i\) thành \(j\) là \(a_{ij}\)). Lưu ý rằng việc chuyển từ nút \(i\) sang một nút trung gian \(k\), rồi từ nút \(k\) sang nút \(j\), có thể tốn ít thời gian hơn so với chuyển trực tiếp từ \(i\) sang \(j\) (hoặc tổng quát hơn, có thể tồn tại một chuỗi thay đổi bắt đầu bằng \(i\) và kết thúc bằng \(j\) cho tổng chi phí tốt nhất để cuối cùng chuyển nút \(i\) thành nút \(j\)).

Hãy giúp Bessie xác định số ngày ít nhất có thể để tạo ra một chuỗi chiêu thức đáp ứng các yêu cầu mới.

Phân nhóm

• Các test 2–4 thỏa mãn \(N \leq 1000\), \(K \leq 50\).
• Các test 5–8 thỏa mãn \(N \leq 30{,}000\), \(K \leq 50\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\), \(M\) và \(K\). Dòng thứ hai chứa \(S\), và \(M\) dòng cuối chứa một ma trận \(M\times M\) các giá trị \(a_{ij}\), trong đó \(a_{ij}\) là một số nguyên thuộc phạm vi \(0 \ldots 1000\) và \(a_{ii}=0\) với mọi \(i\).

Dữ liệu ra

In một số duy nhất, biểu thị số ngày tối thiểu Bessie cần để đổi chuỗi chiêu thức thành một chuỗi thỏa mãn các yêu cầu mới.

Ví dụ

5 5 2
abcde
0 1 4 4 4
2 0 4 4 4
6 5 0 3 2
5 5 5 0 4
3 7 0 5 0

5

Nguồn

USACO 2019 December Contest, Gold - Moortal Cowmbat: https://usaco.org/index.php?page=viewproblem2&cpid=971

Tác giả: Eric Wei.