|
Titlul: 243 Path Scris de: Cosmin Negruseri din Aprilie 12, 2006, 16:31:55 Aici puteţi discuta despre problema Path (http://infoarena.ro/problema/path).
Titlul: Răspuns: 243 Path Scris de: Tirca Bogdan din August 21, 2011, 10:54:01 Am rezolvat problema cu 3 df-uri.
1) caut lungimea drumului maxim 2) fac dinamica: dp[ i ] numarul de drumuri de lungime maxima ce pornesc din nodul i 3) caut al k-lea drum Folosesc 52 de set-uri in loc de matrice, probabil de aici mi se trage TLE (desi 2500 muchii nu mi se par multe). Problema e ca iau si WA, desi pe testele mele merge :| Any help? Titlul: Răspuns: 243 Path Scris de: George Marcus din August 21, 2011, 16:08:21 Punctele 1) si 2) le poti rezolva cu un singur DFS.
Probabil gresesti la punctul 3). (si eu aveam acelasi rezultat cu ideea ta) Consulta GInfo (http://www.ginfo.ro/revista/14_7/concurs.pdf) pentru solutia completa. (problema Drum) |