trang chủ / đề bài / icpc21_reg_b

Mạng trục

Đề bài

Mô tả

FPT Telecom đang lên kế hoạch xây dựng một mạng trục Internet mới để phục vụ khách hàng tốt hơn. Mạng gồm n trạm, đánh số từ 1 đến n, và n−1 đường truyền hai chiều, mỗi đường nối hai trạm khác nhau. Các đường truyền phải đảm bảo mọi cặp trạm đều liên lạc được với nhau. Nói cách khác, mạng phải là một cây.

Độ tin cậy của mạng là kỳ vọng số cặp trạm vẫn còn liên lạc được với nhau khi một đường truyền bị hỏng, giả sử mỗi đường truyền có xác suất hỏng như nhau.

Ví dụ, xét mạng 5 trạm với các đường truyền 1−2, 2−3, 3−4, 2−5:

  • Nếu đường 1−2 hỏng, cả 6 cặp trạm trong số 2,3,4,5 vẫn liên lạc được.
  • Nếu đường 2−3 hỏng, có 4 cặp trạm liên lạc được: (3,4), (1,2), (1,5), (2,5).
  • Nếu đường 3−4 hỏng, cả 6 cặp trạm trong số 1,2,3,5 vẫn liên lạc được.
  • Nếu đường 2−5 hỏng, cả 6 cặp trạm trong số 1,2,3,4 vẫn liên lạc được.

Vậy độ tin cậy của mạng này là 6+4+6+64=5.5.

Dĩ nhiên ta muốn xây dựng mạng có độ tin cậy lớn nhất. Cho số trạm n, hãy xây dựng một mạng như vậy.

Dữ liệu vào

Một dòng chứa số nguyên n.

Dữ liệu ra

  • Dòng đầu tiên chứa một số thực là độ tin cậy lớn nhất của mạng.
  • n−1 dòng tiếp theo, mỗi dòng chứa hai số nguyên u và v (1≤u,v≤n): có một đường truyền nối hai trạm u và v.

Đáp án được coi là đúng nếu sai số tương đối hoặc tuyệt đối không vượt quá 10−6: gọi đáp án của bạn là a và đáp án của ban giám khảo là b, đáp án được chấp nhận khi |a−b|max(1,b)≤10−6. Mạng được in ra phải là một cây có độ tin cậy lớn nhất. Nếu có nhiều cách xây dựng, in cách bất kỳ.

Ràng buộc

  • 2≤n≤50.

Ví dụ

Input Output Giải thích
3 1.000000
1 2
2 3
Đường nào hỏng thì cũng chỉ còn đúng 1 cặp trạm liên lạc được.
5 6.000000
1 2
1 3
1 4
1 5
Ví dụ bổ sung (không có trong đề gốc). Đường nào hỏng thì 4 trạm còn lại vẫn liên lạc được với nhau (6 cặp), tốt hơn mạng 5.5 ở phần mô tả.

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