Codeforces Round #803 (Div. 2)
23:32:01 |
Codeforces Round #804 (Div. 2)
6 өдрийн дараа |
C. Цикллэг будалт
хугацааны хязгаарлалт 4 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
$n$ оройтой, $m$ ирмэгтэй $G$ чиглэлт граф (давхар ирмэг, өрлүүгээ орсон ирмэг байгаа) өгөгдсөн. Та графын орой бүрийг $k (k <= n)$ будгийн нэгээр будах ёстой ба будахдаа $u$ оройгоос $v$ орой хүрэх бүх ирмэгийн хувьд $u$ оройг будсан өнгийн дараагийн өнгөөр $v$ оройг будна.
Өнгүүд 1-ээс $k$-руу цикл байдлаар дугаарлагдана. Энэ нь $i (i < k)$ өнгө бүрийн хувьд дараагийн өнгө $i + 1$ гэсэн үг. Мөн $k$ өнгийн дараагийн өнгө нь 1. Хэрэв $k = 1$ бол 1 өнгийн дараагийн өнгө ахиад л 1 болохыг анхаар.
Таны даалгавар бол $G$ графыг $k$ өнгөөр дээрх дүрсэлсэн байдлаар будахад $k (k <= n)$-ийн хамгийн том утгыг олж хэвлэх. Та бүх $k$ өнгийг хэрэглэх албагүйг анхаар (энэ нь $i$ өнгө бүрийн хувьд $i$ өнгөөр будагдсан орой байх албагүй).
Оролт
Эхний мөр харгалзан оройнуудын тоо, өгөгдсөн чиглэлт графын ирмэгүүдийн тоо болох зайгаар тусгаарлагдсан $n, m (1 <= n, m <= 10^5)$ бүхэл тоог агуулна.
Дараагаар нь $m$ мөр дагалдах ба мөр бүр $a_i$ оройгоос $b_i$ оройд хүрч байгаа $i$ ирмэгийн $a_i, b_i (1 <= a_i, b_i <= n)$ хоосон зайгаар тусгаарлагдсан хоёр бүхэл тоог агуулна.
Давхар ирмэг, өөрлүүгээ орсон ирмэг байгаа.
Гаралт
Чиглэлт графыг будахад хэрэглэгдэх хамгийн их өнгийн тоо ганц бүхэл тоог (энд бодлогод дүрлэгдсэн $k$) хэвлэнэ. $k$-ийн утга $1 <= k <= n$ тэнцэтгэл бишийг хангах ёстой гэдгийг анхаар.
Орчуулсан: devman
Жишээ тэстүүд
Оролт
4 4 1 2 2 1 3 4 4 3
Гаралт
2
Оролт
5 2 1 4 2 5
Гаралт
5
Оролт
4 5 1 2 2 3 3 1 2 4 4 1
Гаралт
3
Оролт
4 4 1 1 1 2 2 1 1 2
Гаралт
1
Тэмдэглэл
Хамгийн эхний жишээнд k = 2 байхад доорх зураг 2 өнгөтэйгөөр зурагдсан (сумууд нь тэр өнгийн дараагийн өнгийг дүрслэнэ).
$k = 2$ байхад графыг будах боломжит арга нь доорх.
% zurag
Энэ жишээнд $k$-ийг өөр том утга байхгүй гэдгийг баталж болно.
% zurag
Хоёр дугаар жишээнд $k = 5$ байх зургийг харуулав.
% zurag
Графыг будах боломжит будалтууд:
% zurag
Гурав дугаар жишээнд $k = 3$ өнгүүд байх зураг.
% zurag
Графыг будах нэг боломжит арга:
% zurag