trang chủ / đề bài / icpc25_reg_e

Thu phí không dừng

Đề bài

Mô tả

Ở một vùng đất xa thật xa, nơi cải cách hành chính bỏ cấp quận chưa được thực hiện, có thành phố Nogias sôi động, được chia thành bốn quận, mỗi quận mang một vẻ đẹp riêng. Quận 1 là "trái tim" của Nogias, nơi đặt các tòa nhà hành chính. Quận 2 là nơi có vô số khu dân cư sang trọng, giàu có. Quận 3 tập trung phần lớn các tòa nhà văn phòng của thành phố. Còn quận 4 được cả người dân Nogias lẫn du khách nước ngoài mệnh danh là thiên đường ẩm thực. Các quận lại được chia thành n phường, đánh số từ 1 đến n, sao cho mỗi quận có ít nhất một phường.

Mạng lưới giao thông của thành phố gồm m con đường hai chiều, mỗi con đường nối hai phường. Có thể có nhiều con đường cùng nối một cặp phường, thậm chí có cả những con đường nối một phường với chính nó: dù sao thì càng nhiều đường càng tốt, mặc kệ chi phí bảo trì. Dữ liệu đảm bảo với mọi cặp phường (u,v), luôn tồn tại ít nhất một đường đi giữa chúng.

Nếu phải chê Nogias một điều, thì đó là vô số vụ kẹt xe. Mỗi ngày, hàng trăm nghìn xe máy tràn ngập các con đường, tạo nên một trải nghiệm thật sự ác mộng. Là một trong những đội xuất sắc nhất của Cuộc thi Quy hoạch Đô thị Quốc tế (ICPC), bạn được hội đồng thành phố thuê để giải quyết vấn đề này. Sau khi phân tích, bạn nhận thấy phần lớn lưu lượng giao thông đến từ những người sống ở một quận nhưng làm việc ở quận khác. Cụ thể, các cặp quận sau đây gây áp lực giao thông rất lớn:

  • quận 1 và quận 2;
  • quận 2 và quận 3;
  • quận 3 và quận 4;
  • quận 4 và quận 1.

Vì không thể di dời người dân, còn đề xuất xây dựng hạ tầng giao thông công cộng của bạn thì bị gạt đi ngay lập tức, bạn chọn phương án duy nhất còn lại: thu phí điện tử không dừng (ETC)! Kế hoạch là lắp đặt ETC trên một số con đường sao cho với mọi cặp quận có vấn đề (x,y), mọi đường đi bắt đầu tại một phường thuộc quận x và kết thúc tại một phường thuộc quận y (hoặc ngược lại) đều phải đi qua ít nhất một con đường có lắp ETC.

Chẳng ai bất ngờ khi kế hoạch thiên tài của bạn được thành phố duyệt ngay, kèm theo một lưu ý nhỏ: người dân thực sự không thích trả tiền. Vì vậy, kế hoạch của bạn còn phải có số con đường được lắp ETC là nhỏ nhất.

Dữ liệu vào

Mỗi file dữ liệu gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số bộ dữ liệu τ (1≤τ≤105). Tiếp theo là mô tả các bộ dữ liệu:

  • Dòng đầu tiên chứa hai số nguyên n và m (4≤n≤105; n−1≤m≤105): số phường và số con đường.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an (1≤ai≤4), trong đó ai là quận chứa phường i.
  • m dòng tiếp theo, mỗi dòng chứa hai số nguyên u và v (1≤u,v≤n), biểu diễn một con đường nối hai phường u và v.

Dữ liệu đảm bảo:

  • Mỗi quận trong bốn quận có ít nhất một phường, và với mọi cặp phường (u,v), luôn tồn tại ít nhất một đường đi giữa chúng.
  • Tổng n qua tất cả các bộ dữ liệu không vượt quá 105.
  • Tổng m qua tất cả các bộ dữ liệu không vượt quá 105.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra số con đường ít nhất cần lắp ETC.

Ràng buộc

  • 1≤τ≤105.
  • 4≤n≤105, n−1≤m≤105.
  • 1≤ai≤4, mỗi quận có ít nhất một phường.
  • 1≤u,v≤n; đồ thị liên thông, có thể có nhiều đường nối cùng một cặp phường và đường nối một phường với chính nó.
  • Tổng n và tổng m qua tất cả các bộ dữ liệu đều không vượt quá 105.

Ví dụ

Input Output Giải thích
1
16 16
1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4
1 4
2 4
3 4
4 8
5 8
6 8
7 8
8 12
9 12
10 12
11 12
12 16
13 16
14 16
15 16
16 4
4 Phường 4, 8, 12, 16 lần lượt là trung tâm của quận 1, 2, 3, 4; các phường còn lại của mỗi quận nối với trung tâm quận mình. Một phương án tối ưu là lắp ETC trên bốn con đường 4−8, 8−12, 12−16 và 16−4.
2
4 3
1 2 3 4
1 2
2 3
3 4
5 7
1 3 2 4 1
1 2
2 3
3 4
4 5
1 2
5 5
4 1
3
3
Ví dụ bổ sung (không có trong đề gốc). Ở bộ dữ liệu thứ nhất, cả ba con đường đều nối một cặp quận có vấn đề. Ở bộ dữ liệu thứ hai, cần lắp ETC trên các con đường 2−3, 4−5 và 4−1; hai con đường 1−2 (quận 1 và quận 3), con đường 3−4 (quận 2 và quận 4) và con đường 5−5 không cần lắp.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0