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 trạm, đánh số từ đến , và đườ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 trạm với các đường truyền , , , :
- Nếu đường hỏng, cả cặp trạm trong số vẫn liên lạc được.
- Nếu đường hỏng, có cặp trạm liên lạc được: , , , .
- Nếu đường hỏng, cả cặp trạm trong số vẫn liên lạc được.
- Nếu đường hỏng, cả cặp trạm trong số vẫn liên lạc được.
Vậy độ tin cậy của mạng này là .
Dĩ nhiên ta muốn xây dựng mạng có độ tin cậy lớn nhất. Cho số trạm , 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 .
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.
- dòng tiếp theo, mỗi dòng chứa hai số nguyên và (): có một đường truyền nối hai trạm và .
Đáp án được coi là đúng nếu sai số tương đối hoặc tuyệt đối không vượt quá : gọi đáp án của bạn là và đáp án của ban giám khảo là , đáp án được chấp nhận khi . 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
- .
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 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ì trạm còn lại vẫn liên lạc được với nhau ( cặp), tốt hơn mạng ở phần mô tả. |
Bình luận