jel moze pomoc oko ovog zadatka, mucim se vec par sati oko njega, ali bez ikakvog napretka:
Dat je usmereni neciklični graf od n čvorova tako da za svaku ivicu а->b, ispunjen je uslov a < b. Naći broj parova čvorova (x, y), x>y tako da ukoliko dodamo ivicu x->y, graf ima hamiltonovu putanju.
1 Like
Пре свега, морамо да проверимо да ли постоји Хамилтонов пут у оригиналном графу. У овом случају, одговор је (n над 2)
У супротном, додавање ивице a → b
може додати Хамилтонову путању само у облику:
(1 → …→ а − 1) →…→ b
б → а
а→…→(б→…n)
Где се ове путање не секу.
Где (x→…→y) значи подразумевану обичну путању x → (x + 1) → … → y.
Користећи ово запажање, лако је извести динамичко програмирање са два стања: два последња врха на чејну, где смо заинтересовани само за стања где су х и х + 1 у различитим чејновима.
dp[ x ][ x + 1 ], dp[ x + 1][ x ], занима нас број добрих парова (а − 1, а) до којих се може доћи из доброг пара (b, b + 1). Где је пар “добар” ако постоји хамилтонова путања у траженом правцу. Одавде можемо добити решење у О(nm), a то би се могло оптимизовати са битсетом на О(nm/64).
Да бисмо линеаризовали решење, можемо уочити да ако нема хамилтонове путање, онда постоји нека ивица y → (y + 1) која није присутна у графу, и сви путеви који повезују чворове за које смо заинтересовани пролазе кроз ову ивицу. Тако да уместо одржавања скупа свих добрих (а, а + 1), можемо да покренемо ДФС у две стране из (у, у + 1), и тако израчунамо режење у линеарној временској сложености.
1 Like
Mozeli pomoc oko prijave za nastavnika informatike