Codeforces Round #804 (Div. 2)
23:53:07 |
Educational Codeforces Round 131 (Rated for Div. 2)
4 өдрийн дараа |
Codeforces Round #805 (Div. 3)
6 өдрийн дараа |
Codeforces Round #806 (Div. 4)
8 өдрийн дараа |
A. Дзи физикт дуртай
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Дзи физикт дуртай. Тэр нягтыг тооцон бодох дуртай.
Бараг бүх зүйлд нягт байдаг, графад ч бас. Чиглэлт бус графын нягтыг дараах байдлаар тодорхойлъё: (графын ирмэг болон орой нь ямар нэгэн утгатай байдаг)
Энд $v$ бол оройнуудын нийлбэр, $e$ бол ирмэгүүдийн нийлбэр.
Дзид $G$ граф байв. Одоо тэр уг графын дэд граф болдог, холбоотой граф $G'$-г олохыг хүсч байна. Энд $G'$-ийн нягт аль болох их байна.
$G(V, E)$ графын $G'(V', E')$ дэд граф нь дараах нөхцөлүүдийг хангасан байна. Үүнд:
;
- Хэрэв
ба ирмэг
байвал ирмэг
байна;
- $G'$ дэх ирмэгийн утга харгалзах $G$ дэх ирмэгийн утгатай ижил бол энэ нь зангилааны утга болно.
Дзид хамгийн их нягтралтай дэд графыг олоход туслаарай. Таны олсон дэд граф холбоотой байх ёстой гэдгийг анхаараарай.
Оролт
Эхний мөр нь зайгаар тусгаарлагдсан $n (1≤n≤500)$, 2 бүхэл тоог агуулна. $n$ бүхэл тоо нь $G$ графын зангилааны тоо, $m$ нь ирмэгийн тоог харуулна.
Дараагийн мөр нь $n$ ширхэг, зайгаар тусгаарлагдсан $x_{i} (1≤x_{i}≤10^{6})$ бүхэл тоонуудыг агуулна. Энд, $x_{i}$ нь $i$-р зангилааны утгыг харуулна. Графын зангилаануудыг $1$-ээс $n$ хүртэл дугаарласан гэж үзнэ.
Дараагийн $m$ мөрүүд тус бүр нь зайгаар тусгаарлагдсан $a_{i}, b_{i}, c_{i} (1≤a_{i} Хариуг дүрслэх, харьцангуй болон үнэмлэхүй алдаа нь хамгийн багадаа $10^{ - 9}$ байх бодит тоог хэвлээрэй.Гаралт
Орчуулсан: Солонго
Жишээ тэстүүд
Оролт
1 0 1
Гаралт
0.000000000000000
Оролт
2 1 1 2 1 2 1
Гаралт
3.000000000000000
Оролт
5 6 13 56 73 98 17 1 2 56 1 3 29 1 4 42 2 3 95 2 4 88 3 4 63
Гаралт
2.965517241379311
Тэмдэглэл
Эхний жишээнд, та хоосон эсвэл зөвхөн $1$ зангилаатай дэд графыг сонгож болох юм.
Хоёр дахь жишээнд графыг бүхлээр нь сонгох хэрэгтэй.