250 Drumuri2

[•filipb]

Aici puteţi discuta despre problema Drumuri2.

[•pauldb]

Totusi, fisierele de intrare si de iesire nu ar trebui sa fie drumuri2.in si drumuri2.out ?

[•filipb]

Am vrut sa las enuntul asa cum era el initial la lot. Numele fisierelor nu trebuie sa fie neaparat identic cu IDul problemei. Am pus drumuri2 pentru ca mai era o problema cu IDul "drumuri" in arhiva.

[•pauldb]

Oricum nu cred ca conteaza atat de mult numele fisierelor de intrare si iesire...doar ca mi se parea mai bine sa fie identice cu numele problemei...That's it 

[Tabara Mihai]

Imi da cineva va rog o idee ? 

[u-92]

hint: flux

[Tabara Mihai]

hint: flux

 

[•gabor_oliviu1991]

Imi spune si mie careva un hint un pic mai complet decat ideea de flux. Ma gandeam ca trebuie sa fac fluxul intre nodurie care au grad interior 0 si cele care au grad exterior 0. Si daca am toate nodurile vizitate afisez numarul de drumuri de ameliorare. Momentan nu prea merge ideea, deci am nevoie de un pic ajutor. Multumesc!

[•Mishu91]

Am o nelămurire. Am citit soluția, dar nu mă prea prind cum "pompez" mai exact fluxul între destinație și sursă, poate cineva să povestească puțin mai mult despre această soluție?

[•dornescuvlad]

Salut.As dori sa stiu daca urmatoarea idee este corecta pentru problema aceasta :

1.Reprezentam graful sub urmatoarea forma :
      - pentru fiecare nod {1,2,...,n} 'stergem muchiile care ies din acesta' (ex 1->4 1->6 sterse pt nodul 1) DAR adaugam un nod v' pentru fiecare nod v astfel incat v' -> 4 si v' -> 6.Muchiile care intra in v le lasam cum sunt initial.Facem legatura v -> v'.
2.Adaugam o sursa virtuala si o destinatie virtuala.Facem legatura sursa -> orice nod v, legatura orice nod v' -> destinatie virtuala.
3.Pornim algoritmul de flux maxim, numarul de pasi in care BFS() == true (adica gasim drum de la sursa la destinatie virtuala) este solutia pt. problema.

Am incercat cateva exemple pe foaie si vad ca da bine..astept si alte pareri de la voi. 

In cazul in care nu e buna solutia asta, m-am mai gandit la ceva in care folosesc si cautare binara? Are cineva vreo solutie cu cautare binara?

[•cosmin79]

Mentionez pentru cine e interesat ca problema se poate reduce la min path cover cu noduri disjuncte intr-un DAG, care poate fi rezolvata cu cuplaj maxim (https://en.wikipedia.org/wiki/Maximum_flow_problem#Minimum_path_cover_in_directed_acyclic_graph).

Reducerea consta in inlocuirea grafului initial cu un graf cu aceleasi noduri, dar muchii orientate x -> y in cazul in care exista un drum de la nodul x la nodul y in graful initial. Pentru a demonstra ca cele 2 probleme sunt echivalente e suficient sa aratam ca orice solutie pe graful initial e o solutie pe graful nou si viceversa.

Daca exista o solutie cu un set de drumuri pe graful initial, poate fi transformat intr-o solutie pe graful nou (fara noduri duplicate) sarind nodurile care au fost vizitate deja (muchiile necesare pt "sarituri" exista din constructie). Pe exemplul problemei:
1 -> 2 -> 3 -> 5 ar ramane tot 1 -> 2 -> 3 -> 5 in graful nou
7 -> 2 -> 4 -> 6, ar deveni:7 -> 4 -> 6 (am sarit nodul 2 fiindca a fost deja vizitat + muchia 7 -> 4 exista din constructie)

Invers, daca exista o acoperire in graful nou, poate fi transformat intr-o solutie pt graful initial inlocuind fiecare muchie x -> y, cu toate nodurile coresp drumului de la x la y.