Cô dâu của dòng ống
Đề bài
Mô tả
Câu chuyện vẫn tiếp diễn! Đã vài năm nay, thị trấn của bạn được "ban tặng" một lượng dồi dào Flubber, một hóa chất nhân tạo đáng yêu nhưng hơi dễ cháy, độc hại, có tính axit, có tri giác và khá tinh nghịch. Người ta vẫn đang tìm thêm công dụng (hay nói đúng hơn là bất kỳ công dụng nào) cho chất này. Trong lúc đó, nhà máy Flubber vẫn chạy hết công suất. Mọi nỗ lực đóng cửa nhà máy đều thất bại, một phần vì chẳng ai chắc ai mới thực sự là người điều hành nó.
Bạn được giao nhiệm vụ chứa dòng Flubber chảy không ngừng vào các bể chứa Flubber để dùng sau này (hoặc ít ra là để nó khỏi làm phiền mọi người). Để làm việc này, bạn có một mạng lưới phức tạp gồm các ống dẫn Flubber nối các trạm Flubber và các bể chứa.
Mỗi trạm Flubber có một hoặc nhiều ống dẫn đi ra, và có các cửa chắn có thể nâng lên hạ xuống để Flubber chảy vào trạm được chia vào các ống ra theo bất kỳ tỉ lệ nào bạn muốn. Chẳng hạn, bạn có thể cho toàn bộ Flubber đi vào một ống, hoặc chia cho hai ống theo tỉ lệ và , v.v.
Ngược lại, một ống dẫn chảy xuống một hoặc nhiều trạm hoặc bể chứa ở thấp hơn, nhưng Flubber trong ống được chia cho chúng theo một tỉ lệ cố định mà bạn không điều khiển được. Có thể một phần Flubber bị thất thoát ra môi trường, nhưng đó là vấn đề của người kế nhiệm bạn chứ không phải của bạn.
Bạn muốn làm đầy tất cả các bể chứa nhanh nhất có thể. Cụ thể, trong mọi cách cấu hình việc chia Flubber ở các trạm, bạn muốn cực đại hóa lượng Flubber nhỏ nhất chảy vào một bể chứa.
Ở ví dụ thứ nhất, trạm có hai ống ra. Ống thứ nhất đưa lượng Flubber vào nó tới bể và tới bể ; ống thứ hai đưa tới trạm và tới bể . Trạm có một ống đưa tới bể . Bạn được chọn tùy ý tỉ lệ Flubber trạm chia cho hai ống của nó, nhưng mỗi ống chia Flubber theo đúng các phần trăm đã ghi.
Dữ liệu vào
Dòng đầu tiên chứa ba số nguyên , và , trong đó () là số trạm, () là số bể chứa, và () là số ống dẫn. Các trạm được đánh số từ đến và các bể chứa được đánh số từ đến , theo thứ tự độ cao giảm dần. Flubber của nhà máy ban đầu chảy vào trạm .
Mỗi dòng trong dòng tiếp theo bắt đầu bằng hai số nguyên và , trong đó () là trạm có thể xả vào ống này, và () là số đầu ra của ống. Phần còn lại của dòng gồm cặp số nguyên và , trong đó () là một trạm hoặc bể chứa mà ống này chảy vào, và () là phần trăm lượng Flubber đi vào ống sẽ chảy tới . Các giá trị của cùng một ống đôi một khác nhau. Mỗi trạm có ít nhất một ống mà nó có thể xả vào. Tổng các phần trăm của các đầu ra của một ống không vượt quá .
Dữ liệu ra
In ra một số phần trăm , là giá trị lớn nhất sao cho với một cách cấu hình việc chia Flubber ở các trạm nào đó, mọi bể chứa đều nhận được ít nhất lượng Flubber nhà máy sản xuất ra. Đáp án của bạn được chấp nhận nếu sai số tuyệt đối không quá .
Ràng buộc
- , , .
- Với mỗi ống: , ; mỗi đầu ra có và ; các của một ống đôi một khác nhau; tổng các của một ống không vượt quá .
- Mỗi trạm có ít nhất một ống.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 3 3 1 2 3 80 4 10 1 2 2 40 4 30 2 1 5 100 |
24.0 | Trạm cho vào ống thứ nhất và vào ống thứ hai. Bể nhận , bể nhận , trạm nhận và chuyển hết cho bể . |
| 1 2 3 1 1 2 50 1 1 3 50 1 2 2 40 3 60 |
42.8571428571 | Chỉ có trạm với ba ống. Cho vào ống thứ nhất và vào ống thứ ba: bể nhận , bể nhận , tức khoảng . |
Bình luận