trang chủ / đề bài / icpcwf17_j

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 v: một ống vận chuyển được v lít/giây nước thì chỉ vận chuyển được 1 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 c là sức chứa nước của ống, còn f và w 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à v·f+w≤c.

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: Fa·W1−a, trong đó F là lưu lượng Flubber đi vào FD, W là lưu lượng nước đi vào FD (lít/giây), và a là một hằng số cho trước nằm giữa 0 và 1.

Hãy tìm giá trị lớn nhất của Fa·W1−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 n, số đường ống p, và hai số thực v, a. Các địa điểm được đánh số từ 1 đến n; địa điểm 1 là nhà máy Flubber, 2 là nguồn nước, 3 là FD. Các số thực có không quá 10 chữ số sau dấu thập phân.

Mỗi dòng trong p dòng tiếp theo mô tả một đường ống gồm hai số nguyên j và k cho biết hai địa điểm mà ống nối, và một số nguyên c 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ừ k sang j), sao cho Fa·W1−a đạt lớn nhất. Sau đó in giá trị lớn nhất đó với sai số tuyệt đối không quá 10−4. 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á 10−4.

Ràng buộc

  • 3≤n≤200.
  • n−1≤p≤n(n−1)/2.
  • 1≤v≤10, 0,01≤a≤0,99.
  • 1≤j<k≤n, 1≤c≤10.

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 2→4, rồi tách thành 4→6→3 (1 lít/giây) và 4→5→3 (0,36 lít/giây); Flubber đi 1→5→3 với 0,88 lít/giây. Ống 3−5 chở cả hai: 3·0,88+0,36=3=c. Có F=0,88, W=1,36 và 0,880,66·1,360,34≈1,0204.
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 2−3 nên F+W≤10, tốt nhất là F=W=5, giá trị 5. Chất lỏng có thể chảy vòng quanh chu trình 3→4→5→3 mà không ảnh hưởng tới kết quả.

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