trang chủ / đề bài / icpc25_mb_e

Đồ thị

Đề bài

Mô tả

Xét một đồ thị vô hướng liên thông gồm n đỉnh và m cạnh. Các đỉnh được đánh số từ 1 đến n và các cạnh được đánh số từ 1 đến m. Bé Đậu Bắn (Peashooter) thực hiện một bước đi ngẫu nhiên trên đồ thị. Ban đầu, Đậu Bắn ở đỉnh 1. Ở mỗi bước, Đậu Bắn chọn ngẫu nhiên một cạnh kề với đỉnh hiện tại với xác suất như nhau, và đi theo cạnh này sang đỉnh tiếp theo, nhận được số điểm bằng số hiệu của cạnh đó. Bước đi kết thúc khi Đậu Bắn đến đỉnh n, và tổng điểm là tổng tất cả số điểm nhận được.

Hãy tìm giá trị kỳ vọng nhỏ nhất của tổng điểm của Đậu Bắn, xét trên mọi cách đánh số m cạnh.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n và m lần lượt là số đỉnh và số cạnh của đồ thị (2≤n≤500).

Mỗi dòng trong m dòng tiếp theo chứa hai số nguyên u,v cho biết có một cạnh nối hai đỉnh u và v (1≤u,v≤n).

Dữ liệu đảm bảo đồ thị liên thông, không có khuyên và không có cạnh lặp.

Dữ liệu ra

In ra một số thực là đáp án, với đúng ba chữ số sau dấu thập phân.

Kết quả được chấp nhận nếu sai số tuyệt đối không vượt quá 10−3 hoặc sai số tương đối không vượt quá 10−6 so với đáp án.

Ràng buộc

  • 2≤n≤500.
  • n−1≤m≤n(n−1)2 (đồ thị liên thông, không có khuyên và cạnh lặp).
  • 1≤u,v≤n, u≠v.

Ví dụ

Input Output Giải thích
3 3
2 3
1 2
1 3
3.333 Cạnh (1,2) được đánh số 1, cạnh (1,3) được đánh số 2, cạnh (2,3) được đánh số 3.
2 1
1 2
1.000 Ví dụ bổ sung (không có trong đề gốc). Đậu Bắn đi đúng một bước theo cạnh duy nhất, có số hiệu 1.

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