trang chủ / đề bài / icpcwf09_e

Cân bằng phí đường

Đề bài

Mô tả

Xử lý ùn tắc giao thông là một thử thách khó đối với các nhà quy hoạch đô thị trẻ. Hàng triệu người lái xe, mỗi người một mục đích và tự đưa ra lựa chọn của mình, cùng tạo nên một hệ thống phức tạp với hành vi lúc thì đoán trước được, lúc thì hỗn loạn. Là một công chức tận tụy, bạn được giao nhiệm vụ tối ưu giao thông giờ cao điểm trên các mạng lưới đường.

Mọi con đường đều nằm giữa một khu dân cư và một khu thương mại trung tâm. Vào buổi sáng, mỗi người sống ở khu dân cư lái xe theo một tuyến đường đến khu thương mại. Dòng xe buổi sáng trên mỗi con đường chỉ đi theo một chiều, và không tuyến đường nào có chu trình (người lái xe buổi sáng không đi vòng lại).

Đi qua mỗi con đường mất một khoảng thời gian nhất định, nên có tuyến đường nhanh hơn những tuyến khác. Người lái xe có xu hướng chọn các tuyến nhanh hơn, dẫn đến ùn tắc trên các con đường đó. Để cân bằng giao thông nhiều nhất có thể, bạn cần đặt phí cầu đường lên một số con đường sao cho "chi phí" cảm nhận được của mọi tuyến đường đều bằng nhau. Tuy nhiên, để không làm người lái xe quá khó chịu, bạn không được thu phí một người lái xe hai lần, dù người đó đi theo tuyến đường nào.

Hình dưới (ví dụ 1, trường hợp 1) gồm năm con đường tạo thành các tuyến đường từ khu dân cư (giao lộ 1) đến khu thương mại (giao lộ 4); số trên mỗi con đường là chi phí lái xe của nó. Có ba tuyến đường từ 1 đến 4: 1→4, 1→3→4 và 1→3→2→4, ban đầu có chi phí lần lượt là 10, 8 và 12. Sau khi đặt phí 2 lên con đường từ 1 đến 4 và phí 4 lên con đường từ 3 đến 4, chi phí của mỗi tuyến đường đều trở thành 12: 10+2, 5+3+4 và 5+1+6.

graph directed weighted
4 5
1 3 5
3 2 1
2 4 6
1 4 10
3 4 3
pos 1 0 0
pos 4 360 0
pos 3 160 100
pos 2 300 180
highlight red 1-4 3-4

Bạn cần xác định những con đường nào phải đặt phí và mức phí của mỗi con đường bằng bao nhiêu, sao cho mọi tuyến đường từ điểm xuất phát đến điểm đích có cùng chi phí (thời gian lái xe cộng phí, nếu có) và không tuyến đường nào chứa quá một con đường có thu phí. Ngoài ra, các mức phí phải được chọn sao cho chi phí cuối cùng là nhỏ nhất. Trong một số trường hợp, có thể không đặt được phí thỏa mãn các điều kiện trên.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên N và R: N là số giao lộ, R là số con đường. Mỗi dòng trong R dòng tiếp theo chứa ba số nguyên xi, yi và ci, cho biết dòng xe buổi sáng đi trên con đường i từ giao lộ xi đến giao lộ yi với chi phí lái xe cơ bản là ci. Giao lộ 1 là khu dân cư xuất phát, giao lộ N là khu thương mại đích. Các con đường được đánh số từ 1 đến R theo thứ tự trong dữ liệu vào. Mọi giao lộ đều nằm trên một tuyến đường nào đó từ 1 đến N, và không có chu trình.

Sau bộ test cuối cùng là một dòng chứa hai số 0.

Dữ liệu ra

Với mỗi bộ test, in một dòng gồm số thứ tự của bộ test (bắt đầu từ 1), số con đường được đặt phí T và chi phí cuối cùng của mọi tuyến đường. Trong T dòng tiếp theo, mỗi dòng in số hiệu i của một con đường và mức phí (số nguyên dương) đặt lên con đường đó. Nếu có nhiều cách đặt phí đạt chi phí nhỏ nhất, in cách nào cũng được. Nếu không có cách nào, in No solution. Làm theo đúng định dạng trong ví dụ.

Ràng buộc

  • 2≤N≤50000, 1≤R≤50000.
  • 1≤xi,yi≤N, 1≤ci≤1000.
  • Có thể có nhiều con đường nối cùng một cặp giao lộ.
  • Mỗi file có không quá 104 bộ test và tổng R không quá 3·105.

Ví dụ

Input Output Giải thích
4 5
1 3 5
3 2 1
2 4 6
1 4 10
3 4 3
3 4
1 2 1
1 2 2
2 3 1
2 3 2
0 0
Case 1: 2 12
4 2
5 4
Case 2: No solution
Trường hợp 1 là hình trên. Trường hợp 2: hai con đường 1→2 có chi phí khác nhau và hai con đường 2→3 cũng vậy, nên phải thu phí cả trên một con đường 1→2 lẫn trên một con đường 2→3, tức là có tuyến đường bị thu phí hai lần.
3 3
1 2 4
2 3 3
1 3 7
5 6
1 2 1
1 3 2
2 4 1
3 4 1
4 5 1
1 5 1
4 5
1 2 1
1 2 2
2 3 1
3 4 1
3 4 2
0 0
Case 1: 0 7
Case 2: 2 4
3 1
6 3
Case 3: No solution
Trường hợp 1: mọi tuyến đường đã có chi phí 7, không cần đặt phí. Trường hợp 2: chi phí cuối cùng là 4 (tuyến dài nhất 1→3→4→5); đặt phí 1 lên con đường 3 (2→4) và phí 3 lên con đường 6 (1→5). Đặt phí 1 lên con đường 1 (1→2) thay cho con đường 3 cũng đúng. Trường hợp 3: các tuyến từ 1 đến 3 có chi phí 2 hoặc 3, các tuyến từ 3 đến 4 có chi phí 1 hoặc 2, nên không có lời giải.

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