Con trai của dòng ống
Đề bài
Mô tả
Hai năm trước, bạn đã giúp lắp đặt mạng ống dẫn Flubber đầu tiên của cả nước tại thành phố quê hương, và nó thành công rực rỡ. Các cuộc thăm dò cho thấy ai cũng thích có một vòi Flubber riêng trong bếp, và giờ đây vài người dân năng động đã tìm ra một công dụng mới cho nó: Flubber khi trộn với nước có thể giúp dập lửa! Phát hiện này rất đúng lúc, vì gần đây các đám cháy mất kiểm soát xảy ra thường xuyên một cách đáng ngạc nhiên.
Hội đồng thành phố muốn tận dụng tính chất này bằng cách tạo hỗn hợp Flubber/nước tại một trạm đặt ở trung tâm. Trạm này, gọi là Sở Flubber (FD), cũng có các nhân viên được huấn luyện để đến nơi có cháy và dùng Flubber đã xử lý để khống chế đám cháy.
Các đường ống đã được lắp sẵn khắp thành phố. Bạn được cho sơ đồ các đường ống và phải xác định cách dẫn Flubber từ nhà máy Flubber và nước từ một nguồn nước địa phương qua các đường ống đến FD. Lưu ý rằng cả Flubber và nước đều chảy trong cùng một mạng ống, thậm chí có thể trong cùng một ống. Mọi ống đều hai chiều, nhưng Flubber và nước không được chảy ngược chiều nhau trong cùng một ống. Ngoài ra, nếu cả hai chất lỏng được dẫn cùng chiều trong cùng một ống thì chúng chắc chắn sẽ trộn lẫn. Vì vậy các nút của mạng đã được trang bị màng lọc đặc biệt cho phép tách và sắp xếp lại mọi hỗn hợp đi vào theo ý bạn.
Mạng là một hệ kín, nên tổng lưu lượng của mỗi chất lỏng đi vào một nút phải bằng tổng lưu lượng chất đó đi ra, trừ tại nguồn của chất lỏng đó và tại đích (FD).
Mỗi ống có một sức chứa nhất định. Flubber khá sệt nên có độ nhớt : một ống vận chuyển được lít/giây nước thì chỉ vận chuyển được lít/giây Flubber. Sức chứa thay đổi tuyến tính với hỗn hợp của hai chất. Chính xác hơn, nếu là sức chứa nước của ống, còn và là lưu lượng Flubber và nước chảy trong ống (đều tính bằng lít/giây), thì ràng buộc sức chứa là .
Mối quan tâm chính của bạn là cân bằng hỗn hợp đến FD. Bạn muốn tổng lượng chất lỏng càng nhiều càng tốt, nhưng cũng cần đủ nước (vì Flubber nguyên chất rất dễ cháy) và đủ Flubber (vì nếu không có Flubber thì chẳng còn là "Sở Flubber"!). Bạn đưa ra công thức đo "giá trị" của hỗn hợp cuối cùng: , trong đó là lưu lượng Flubber đi vào FD, là lưu lượng nước đi vào FD (lít/giây), và là một hằng số cho trước nằm giữa và .
Hãy tìm giá trị lớn nhất của có thể đạt được và cách dẫn Flubber và nước để đạt giá trị đó.
Dữ liệu vào
Dòng đầu tiên chứa số địa điểm , số đường ống , và hai số thực , . Các địa điểm được đánh số từ đến ; địa điểm là nhà máy Flubber, là nguồn nước, là FD. Các số thực có không quá chữ số sau dấu thập phân.
Mỗi dòng trong dòng tiếp theo mô tả một đường ống gồm hai số nguyên và cho biết hai địa điểm mà ống nối, và một số nguyên là sức chứa nước của ống (lít/giây).
Không có hai ống nối cùng một cặp địa điểm. Dữ liệu đảm bảo mạng liên thông.
Dữ liệu ra
Đầu tiên, với mỗi ống (theo thứ tự trong dữ liệu vào), in hai giá trị trên một dòng: lưu lượng Flubber và lưu lượng nước chảy qua ống đó (mang dấu âm nếu chất lỏng chảy từ sang ), sao cho đạt lớn nhất. Sau đó in giá trị lớn nhất đó với sai số tuyệt đối không quá . Nếu có nhiều lời giải, in lời giải nào cũng được.
Mọi ràng buộc (Flubber và nước không chảy ngược chiều nhau trong cùng một ống, bảo toàn lưu lượng, sức chứa của ống, và sự khớp giữa cách dẫn đã in với giá trị đã in) phải được thỏa mãn với sai số tuyệt đối không quá .
Ràng buộc
- .
- .
- , .
- , .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 6 3.0 0.66 2 4 8 4 6 1 3 6 1 4 5 5 1 5 7 3 5 3 |
0.000000000 1.360000000 0.000000000 1.000000000 0.000000000 -1.000000000 0.000000000 0.360000000 0.880000000 0.000000000 -0.880000000 -0.360000000 1.02037965897 |
Nước đi , rồi tách thành ( lít/giây) và ( lít/giây); Flubber đi với lít/giây. Ống chở cả hai: . Có , và . |
| 5 5 1.0 0.5 1 2 10 2 3 10 3 4 10 4 5 10 3 5 10 |
5 0 5 5 4.2 3.14159 4.2 3.14159 -4.2 -3.14159 5 |
Mọi chất lỏng phải đi qua ống nên , tốt nhất là , giá trị . Chất lỏng có thể chảy vòng quanh chu trình mà không ảnh hưởng tới kết quả. |
Bình luận