|
Titlul: Lant maxim in arbore Scris de: Parfene Narcis din Ianuarie 17, 2013, 16:16:15 La multi ani tuturor!
V-as ruga sa ma ajutati la urmatoarea problema: Fie un arbore (graf conex fara cicluri). Sa se determine un lant elementar de lungime maxima. Daca as face un BF din fiecare nod, as avea o complexitate O(n x (n + m)). As putea reduce poate ceva daca fac BF numai din noduri terminale. Intrebarea mea este: exista un algoritm mai bun? Multumesc! Titlul: Răspuns: Lant maxim in arbore Scris de: Salajan Razvan din Ianuarie 17, 2013, 16:19:44 Da, este. Se poate in (n + m). Cred ca problema aceasta (http://infoarena.ro/problema/razboi) cere acelasi lucru.
Titlul: Răspuns: Lant maxim in arbore Scris de: Mihai Calancea din Ianuarie 17, 2013, 17:56:26 Cea mai evidenta solutie e o dinamica dp[nod] = cel mai lung lant in jos pornind din nod. Evident in fiecare nod ai sa incerci apoi sa unesti fii cu dp maxim.
Alta solutie mai simpla ar fi sa faci un DF. Vei obtine un nod X, cu distanta cea mai mare de radacina. Daca mai faci un df din X si nodul cu cea mai mare distanta fata de el este Y, atunci X - Y este un lant de lungime maxima. Titlul: Răspuns: Lant maxim in arbore Scris de: Parfene Narcis din Ianuarie 17, 2013, 18:28:37 Multumesc pentru sfaturi!
Mi se pare interesanta ideea cu exact doua DF-uri, desi nu-mi dau seama cum se arata (macar intuitiv) corectitudinea algoritmului. Titlul: Răspuns: Lant maxim in arbore Scris de: Andrei Grigorean din Ianuarie 17, 2013, 22:22:02 Hint: Trebuie sa demonstrezi ca oricare ar fi un nod X din arbore, cea mai departata frunza de X va face parte intotdeauna dintr-un lant de lungime maxima. Se face prin reducere la absurd.
|