trang chủ / đề bài / icpcwf12_g

Dẫn nước chi phí nhỏ nhất

Đề bài

Mô tả

Bạn được thuê xây dựng một hệ thống dẫn nước giữa hai điểm trong một nhà xưởng cũ, sử dụng một số bộ phận của hệ thống ống nước cũ còn sót lại. Các bộ phận cũ gồm các ống và các mối nối. Mối nối là những điểm mà trước đây các ống có thể được nối với nhau. Ta nói "trước đây" vì một số ống cũ đã hỏng và bị tháo đi, để lại những lỗ hở ở các mối nối mà chúng từng gắn vào. Nếu nước chảy vào một mối nối như vậy, nước sẽ tràn ra qua lỗ hở và cuối cùng làm ngập tòa nhà, điều hiển nhiên không mong muốn.

Bạn có thể khắc phục bằng cách lắp ống mới giữa một số lỗ hở và lắp nút bịt để bịt các lỗ hở khác khi cần. Khi lắp một ống mới nối hai lỗ (hai lỗ này phải nằm ở hai mối nối khác nhau), hai lỗ đó không còn hở nữa và nước có thể chảy qua ống mới. Chi phí lắp một ống mới bằng khoảng cách giữa tâm hai mối nối mà ống đó nối. Chi phí bịt một lỗ hở là 0,5. Bạn không cần quan tâm tới các lỗ hở ở những mối nối mà nước không bao giờ chảy tới.

Có hai mối nối đặc biệt. Mối nối thứ nhất, gọi là nguồn, là nơi nước được bơm vào hệ thống mới. Mối nối thứ hai, gọi là đích, là nơi cần có nước. Sau khi đã lắp xong các nút bịt và ống mới, nước được bơm vào hệ thống tại nguồn với áp suất đủ để đẩy nước lên tới một độ cao nhất định (khi không có chỗ rò rỉ). Bạn được chọn áp suất tùy ý, và áp suất được bảo đảm không thay đổi trong suốt quá trình hệ thống hoạt động. Dĩ nhiên áp suất phải đủ để đẩy nước lên tới độ cao của cả nguồn lẫn đích. Nhiệm vụ của bạn chỉ đơn giản là tìm cách rẻ nhất để đưa nước từ mối nối nguồn tới mối nối đích mà không làm ngập tòa nhà.

Hình dưới đây ứng với bộ test đầu tiên của ví dụ: mối nối 1 là nguồn và mối nối 7 là đích (tô xám), ghi chú cạnh mỗi mối nối là số lỗ hở của nó; mối nối càng cao trong hình thì có độ cao z càng lớn.

graph
1 2
1 3
3 4
4 7
5 7
6 7
pos 1 120 180
pos 2 0 240
pos 3 60 0
pos 4 180 0
pos 5 300 180
pos 6 180 120
pos 7 240 60
highlight gray 1 7
label 1 1 lỗ
label 2 2 lỗ
label 3 3 lỗ
label 4 3 lỗ
label 5 1 lỗ
label 6 0 lỗ
label 7 0 lỗ

Nước chảy trong hệ thống theo các định luật vật lý. Nếu áp suất đủ để làm đầy một mối nối thì mối nối đó luôn đầy nước. Nếu từ một mối nối có các ống đi ngang hoặc đi xuống thì nước cũng chảy qua các ống đó. Nước cũng chảy ngược lên theo các ống nối với một mối nối, nhưng chỉ tới độ cao do áp suất quyết định. Tất nhiên, nếu nước chạm tới một lỗ hở ở một mối nối, nó sẽ chảy ra qua lỗ và làm ngập tòa nhà.

Trong bộ test đầu tiên của ví dụ, bạn có thể nối mối nối 1 với mối nối 5 với chi phí 3, bịt các lỗ hở ở mối nối 2, và đặt áp suất sao cho nước chỉ dâng lên tới mối nối 7. Khi đó nước làm đầy các mối nối 1, 2, 5, 6 và 7, và không dâng cao hơn. Một cách khác (đắt hơn) là bịt tất cả các lỗ với tổng chi phí 5 và để nước chảy qua mọi mối nối. Bạn không thể giải bộ test này bằng cách nối mối nối 1 với mối nối 6 rồi bịt các lỗ ở mối nối 2 và 5, vì mối nối 6 không có lỗ hở nào để gắn ống mới.

Giả sử các ống có sẵn và các ống mới không cản trở nhau, cũng không chạm vào bất kỳ mối nối nào ngoài hai mối nối mà chúng nối. Nghĩa là, kể cả khi đoạn thẳng từ mối nối A tới mối nối B đi qua mối nối C, một ống nối A với B cũng không chạm vào C.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test, đọc tới hết file. Dòng đầu tiên của mỗi bộ test gồm hai số nguyên N và M, trong đó N (2≤N≤400) là số mối nối trong tòa nhà (đánh số từ 1 tới N) và M (0≤M≤50000) là số ống cũ còn dùng được.

Mỗi dòng trong N dòng tiếp theo gồm bốn số nguyên xi, yi, zi và ki (−10000≤xi,yi,zi≤10000, 0≤ki≤400), với i=1,2,…,N. Dòng thứ i mô tả mối nối i: (xi,yi,zi) là vị trí của mối nối, trong đó trục z là trục thẳng đứng; ki là số lỗ hở ở mối nối đó.

Mỗi dòng trong M dòng tiếp theo gồm hai số nguyên aj và bj (1≤aj<bj≤N), cho biết ống thứ j nối hai mối nối aj và bj. Giữa hai mối nối có nhiều nhất một ống, và không có hai mối nối nào trùng tọa độ. Nguồn là mối nối 1, đích là mối nối N.

Dữ liệu ra

Với mỗi bộ test, in ra số thứ tự của bộ test theo định dạng trong ví dụ. Sau đó, nếu có thể dùng các ống mới và nút bịt phù hợp để xây dựng hệ thống, in ra chi phí nhỏ nhất để nối mối nối nguồn với mối nối đích, chính xác tới bốn chữ số thập phân. Nếu không thể nối nguồn với đích, in ra từ impossible.

Ràng buộc

  • 2≤N≤400, 0≤M≤50000.
  • −10000≤xi,yi,zi≤10000, 0≤ki≤400.
  • 1≤aj<bj≤N; giữa hai mối nối có nhiều nhất một ống; các mối nối có tọa độ đôi một khác nhau.

Ví dụ

Input Output Giải thích
7 6
2 0 1 1
0 0 0 2
1 0 4 3
3 0 4 3
5 0 1 1
3 0 2 0
5 0 3 0
1 2
1 3
3 4
4 7
5 7
6 7
4 1
2 0 0 0
3 0 1 0
4 1 0 1
5 1 1 1
1 2
Case 1: 4.0000
Case 2: impossible
Bộ 1: nối lỗ của mối nối 1 với lỗ của mối nối 5 (dài 3), bịt 2 lỗ của mối nối 2 (chi phí 1), đặt mực nước ở độ cao 3 của mối nối 7; tổng 4. Bộ 2: nước từ nguồn chỉ tới được mối nối 2; nguồn và mối nối 2 không có lỗ hở nào để lắp ống mới nên không thể đưa nước tới mối nối 4.
3 0
0 0 0 1
1 0 0 1
2 0 0 1
Case 1: 2.0000 Ba mối nối thẳng hàng, mỗi mối nối có một lỗ. Không thể đi qua mối nối 2 (một lỗ không đủ cho cả ống vào lẫn ống ra), nên nối thẳng lỗ của mối nối 1 với lỗ của mối nối 3 (dài 2); mối nối 2 không có nước nên không cần bịt. Tổng 2.

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