trang chủ / đề bài / icpc23_reg_k

Lợi nhuận của nhà vua

Đề bài

Mô tả

Một vương quốc có n thành phố và m con đường một chiều, các thành phố được đánh số từ 1 đến n và các con đường được đánh số từ 1 đến m. Con đường thứ i đi từ thành phố ui đến thành phố vi. Có thể có nhiều con đường nối cùng một cặp thành phố, nhưng không có con đường nào nối một thành phố với chính nó. Vương quốc có hai thành phố quan trọng: thủ đô là thành phố 1, và thành phố trung tâm là thành phố n. Biết rằng có ít nhất một đường đi từ thủ đô đến thành phố trung tâm.

Nhà vua muốn thu thuế người dân càng nhiều càng tốt, nên ông bắt đầu xây các trạm thu phí trên các con đường. Mỗi trạm thu phí xây trên con đường thứ i mang lại cho nhà vua ai đô la. Lưu ý rằng trên một con đường có thể xây nhiều trạm thu phí.

Dễ hiểu là việc này khiến người dân bất bình và phản đối việc xây trạm thu phí tràn lan. Để xoa dịu người dân, nhà vua quyết định xây các công viên giải trí. Xây một công viên giải trí trên con đường thứ i tốn của nhà vua bi đô la. Tương tự trạm thu phí, trên một con đường có thể xây nhiều công viên giải trí.

Để người dân không phản đối thêm, nhà vua sẽ xây trạm thu phí và công viên giải trí sao cho với mọi đường đi từ thủ đô đến thành phố trung tâm, hiệu giữa số trạm thu phí và số công viên giải trí không vượt quá một giá trị cho trước. Cụ thể, với một đường đi từ thủ đô đến thành phố trung tâm lần lượt đi qua các con đường có chỉ số r1,r2,…,rk, điều kiện sau phải được thoả mãn:

∑j=1kBrj−∑j=1kPrj≤c

trong đó

  • Brj là số trạm thu phí nhà vua xây trên con đường thứ rj;
  • Prj là số công viên giải trí nhà vua xây trên con đường thứ rj;
  • c là mức chịu đựng của người dân mà nhà vua đã khảo sát được.

Nói cách khác, với mọi đường đi từ thủ đô đến thành phố trung tâm, nhà vua muốn số trạm thu phí không vượt quá số công viên giải trí quá c đơn vị. Lưu ý rằng ta xét mọi đường đi, kể cả các đường đi qua cùng một thành phố hoặc cùng một con đường nhiều lần. Khi đó, các phần tử của dãy r1,r2,…,rk trong biểu thức trên có thể không phân biệt.

Đương nhiên, nhà vua vẫn muốn lợi nhuận lớn nhất (tổng tiền thu từ các trạm thu phí trừ tổng chi phí xây các công viên giải trí). Cho bản đồ vương quốc, mức chịu đựng c của người dân, cùng chi phí và lợi nhuận khi xây các công trình, hãy giúp nhà vua tính lợi nhuận lớn nhất có thể khi xây dựng tối ưu, hoặc cho biết tồn tại một phương án xây dựng giúp nhà vua thu được nhiều hơn 1018 đô la.

Nhắc lại, một đường đi từ thủ đô đến thành phố trung tâm có thể biểu diễn bởi một dãy chỉ số con đường r1,r2,…,rk thoả mãn:

  • ur1=1;
  • vrj=urj+1 với mọi 1≤j<k;
  • vrk=n.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên t (1≤t≤20000), số bộ dữ liệu. Tiếp theo là t bộ dữ liệu, mỗi bộ có dạng:

  • Dòng đầu tiên chứa ba số nguyên n, m và c (2≤n≤1000, 1≤m≤1000, 1≤c≤106): số thành phố, số con đường của vương quốc và mức chịu đựng của người dân.
  • m dòng tiếp theo, dòng thứ i chứa bốn số nguyên ui, vi, ai và bi (1≤ui,vi≤n, ui≠vi, 0≤ai,bi≤106) mô tả con đường thứ i: con đường đi từ thành phố ui đến thành phố vi, mỗi trạm thu phí trên con đường mang lại ai đô la và mỗi công viên giải trí trên con đường tốn bi đô la. Dữ liệu bảo đảm có ít nhất một đường đi từ thủ đô đến thành phố trung tâm.

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

  • Tổng n2 của tất cả các bộ dữ liệu không vượt quá 106.
  • Tổng m2 của tất cả các bộ dữ liệu không vượt quá 106.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng:

  • −1 nếu tồn tại một phương án xây dựng giúp nhà vua thu được nhiều hơn 1018 đô la;
  • ngược lại, một số nguyên là lợi nhuận lớn nhất nhà vua có thể đạt được khi xây dựng tối ưu.

Ràng buộc

  • 1≤t≤20000
  • 2≤n≤1000, 1≤m≤1000, 1≤c≤106
  • 1≤ui,vi≤n, ui≠vi, 0≤ai,bi≤106
  • Tổng n2 và tổng m2 của tất cả các bộ dữ liệu đều không vượt quá 106.

Ví dụ

Input Output Giải thích
4
2 1 2
1 2 3 8
2 4 3
1 2 6 10
1 2 1 3
2 1 2 7
2 1 0 3
6 8 1
3 6 4 8
1 5 0 6
1 3 0 3
5 4 1 3
6 3 5 10
5 4 5 7
5 6 3 10
4 5 5 8
4 4 5
1 2 4 5
1 2 3 1
2 4 3 3
3 1 9 6
6
0
3
-1
Bộ thứ nhất: xây 2 trạm thu phí trên con đường thứ nhất, lợi nhuận 6. Bộ thứ hai: chỉ cần xây 1 trạm thu phí trên con đường thứ nhất là người dân đã phản đối, vì đường đi qua các con đường 1,3,1,3,1,3,1 gặp 4 trạm thu phí mà không có công viên nào; nhà vua không thể có lãi. Bộ thứ tư: có thể xây 1018 trạm thu phí trên con đường thứ tư vì nó không nằm trên đường đi nào từ thủ đô đến thành phố trung tâm.
3
2 2 7
1 2 2 5
2 1 0 5
3 3 4
1 3 1 2
3 2 0 4
2 3 1 1
4 3 5
1 4 2 3
2 3 1 1
3 2 1 1
0
4
-1
Ví dụ bổ sung. Bộ thứ ba: hai con đường giữa thành phố 2 và 3 không nằm trên đường đi nào từ thủ đô đến thành phố trung tâm.

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