Codeforces Round #804 (Div. 2)
22:45:48 |
Educational Codeforces Round 131 (Rated for Div. 2)
4 өдрийн дараа |
Codeforces Round #805 (Div. 3)
6 өдрийн дараа |
Codeforces Round #806 (Div. 4)
8 өдрийн дараа |
E. Пашмак ба граф
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Пашмакийн даалгавар нь графийн бодлого байв. Хэдийгээр тэр чадахаараа оролдсон ч бодож чадахгүй л байна. Таны мэдэж байгаачлан тэр графийн онолд үнэхээр тааруу юм, тэгэхээр түүнд бодлогоо бодоход нь тусална уу.
$n$ оройтой $m$ ирмэгтэй жинтэй чиглэлтэй граф ѳгѳгдсѳн. Замын турш таарах ирмэгүүдийн жин ѳсдѳг байх хамгийн их ирмэгтэй замыг олох шаардлагатай. Ѳѳрѳѳр хэлбэл уг замын ирмэг бүр ѳмнѳх ирмэгээсээ илүү жинтэй байна.
Пашмакд тусалж, шаардлагатай замын ирмэгүүдийн тоог хэвлэнэ үү.
Оролт
Эхний мѳрѳнд $n$, $m$ $(2 ≤ n ≤ 3*10^{5}; 1 ≤ m ≤ min(n*(n - 1), 3*10^{5}))$ бүхэл тоо байрлана. Тэгээд дараа нь $m$ мѳр байрлана. $i$-р мѳр нь зайгаар тусгаарлагдсан $u_{i}$, $v_{i}$, $w_{i}$ $(1 ≤ u_{i}, v_{i} ≤ n; 1 ≤ w_{i} ≤ 10^{5})$ бүхэл тоонуудыг агуулна. Энэ нь $u_{i}$, $v_{i}$ оройнууд $w_{i}$ жинтэй ирмэгээр холбогдсоныг илтгэнэ.
Уг графд гогцоо болон давхар ирмэг байхгүй.
Гаралт
Бодлогын хариу болох ганц тоог хэвлэ.
Орчуулсан: Sugardorj
Жишээ тэстүүд
Оролт
3 3 1 2 1 2 3 1 3 1 1
Гаралт
1
Оролт
3 3 1 2 1 2 3 2 3 1 3
Гаралт
3
Оролт
6 7 1 2 1 3 2 5 2 4 2 2 5 2 2 6 9 5 4 3 4 3 4
Гаралт
6
Тэмдэглэл
Нэгдүгээр жишээний хувьд дараах замуудын аль нь ч байж болно: .
Хоёрдугаар жишээний хувьд хамгийн их ирмэгтэй зам нь .
Гуравдугаар жишээний хувьд хамгийн их ирмэгтэй зам нь .