D. Граф тоглоом

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Компьютерийн шинжлэх ухаанд "Зангилаагаар хуваагаад давах" гэсэн нэртэй мод дээрх зарим хэцүү замын бодлогуудыг шийдэх арга байдаг. Уг аргыг хэрхэн ажилладагийг функцээр тодорхойлье:

$solve(t)$ ($t$ бол мод):

  1. $t$ мод дахь $x$ зангилааг (хүндийн төвийг сонгох нь элбэг) сонгоно. Энэ алхмыг "A шугам" гэе.
  2. $x$-г дайран өнгөрч буй бүх замыг ойлгох.
  3. Тэгээд $t$ модноос $x$ зангилааг устгах.
  4. Үүний дараа $t$ нь хэд хэдэн дэд модтой болно.
  5. Дэд мод бүр дээр $solve$-г дуудах.

Энэ үйлдэл нь $t$ зөвхөн нэг зангилаатай үлдэх үед дуусна учир нь энэ зангилааг устгавал юу ч үлдэхгүй.

Одоо WJMZBMR маань "А Шугам" дээр дурын зангилааг сонгох нь асуудалгүй гэж эндүүрч байна. Ингээд тэр зангилааг санамсаргүйгээр сонгоно. Нөхцөл байдлыг илүү хүнд болгох үүднээс тэр модыг ижил тооны ирмэг болон зангилаатай байх ёстой гэж бодож байна. Ингээд энэ үйл явц нь дараах байдалтай болж ирнэ.

$totalCost$ хувьсагчийг тодорхойлцгооё. Анх $totalCost$ хувьсагчийн утга $0$ байна. Ингээд $solve(t)$ (одоо $t$ нь граф):

  1. $totalCost = totalCost + (size of t)$. "$=$" үйлдэл нь оноох үйлдэл юм. (Size of t) гэдэг нь $t$ дахь зангилаануудын тоо байна.
  2. $t$ граф дахь $x$ зангилааг санамсаргүйгээр сонгоно ($t$-н бүх зангилаан дундаас).
  3. Тэгээд $t$ графаас $x$ зангилааг устгана.
  4. Үүний дараа $t$ маань холбогдсон хэд хэдэн хэсэг болно.
  5. Хэсэг бүр дээр $solve$-г дуудна.

Тэр $solve$-г $n$ зангилаа $n$ ирмэгтэй холбогдсон граф дээр дуудна. Тэр үүнийг хурдан ажиллах болно гэж бодож байгаа боловч энэ нь маш удаан. Ингээд тэр энэ үйл явцын $totalCost$-н таамаг утгыг мэдэхийг хүсч байна. Та түүнд туслаж чадах уу?

Оролт

Эхний мөрөнд бүхэл тоо $n$ ($3 ≤ n ≤ 3000$) байх ба граф дахь зангилаа болон ирмэгийн тоо. Дараагийн $n$ мөр бүрт зайгаар тусгаарлагдсан хоёр бүхэл тоо $a_{i}, b_{i}$ $(0 ≤ a_{i}, b_{i} ≤ n - 1)$ байх ба $a_{i}$ ба $b_{i}$ зангилаануудын хооронд байгаа ирмэгийг илтгэнэ.

Графийн зангилаанууд $0$-с $(n - 1)$ хүртэл дугаарлагдсан гэж үз. Энэ графд өөртэйгээ холбогдсон болон давхар ирмэг байхгүй. Граф холбогдсон байна.

Гаралт

$totalCost$-н таамаг утгыг илэрхийлэх нэг бодит тоог хэвлэ. Хэрвээ таны хариултын үнэмлэхүй эсвэл харьцангуй алдаа $10^{ - 6}$-с ихгүй бол зөвд тооцно.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
5
3 4
2 3
2 4
0 4
1 2
Гаралт
13.166666666666666
Оролт
3
0 1
1 2
0 2
Гаралт
6.000000000000000
Оролт
5
0 1
1 2
2 0
3 0
4 1
Гаралт
13.166666666666666

Тэмдэглэл

Хоёр дахь жишээг авч үзье. Бид эхлээд юу сонгох нь хамаагүй $totalCost$ үргэлж $3 + 2 + 1 = 6$ байна.

Сэтгэгдлүүдийг ачааллаж байна...