Lợi nhuận của nhà vua
Đề bài
Mô tả
Một vương quốc có thành phố và con đường một chiều, các thành phố được đánh số từ đến và các con đường được đánh số từ đến . Con đường thứ đi từ thành phố đến thành phố . 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ố , và thành phố trung tâm là thành phố . 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ứ mang lại cho nhà vua đô 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ứ tốn của nhà vua đô 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ố , điều kiện sau phải được thoả mãn:
trong đó
- là số trạm thu phí nhà vua xây trên con đường thứ ;
- là số công viên giải trí nhà vua xây trên con đường thứ ;
- 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á đơ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 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ủ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 đô 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 thoả mãn:
- ;
- với mọi ;
- .
Dữ liệu vào
Dòng đầu tiên chứa số nguyên (), số bộ dữ liệu. Tiếp theo là bộ dữ liệu, mỗi bộ có dạng:
- Dòng đầu tiên chứa ba số nguyên , và (, , ): 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.
- dòng tiếp theo, dòng thứ chứa bốn số nguyên , , và (, , ) mô tả con đường thứ : con đường đi từ thành phố đến thành phố , mỗi trạm thu phí trên con đường mang lại đô la và mỗi công viên giải trí trên con đường tốn đô 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 của tất cả các bộ dữ liệu không vượt quá .
- Tổng của tất cả các bộ dữ liệu không vượt quá .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra trên một dòng:
- 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 đô 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
- , ,
- , ,
- Tổng và tổng của tất cả các bộ dữ liệu đều không vượt quá .
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 trạm thu phí trên con đường thứ nhất, lợi nhuận . Bộ thứ hai: chỉ cần xây 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 gặp 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 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ố và không nằm trên đường đi nào từ thủ đô đến thành phố trung tâm. |
Bình luận