flux in graf neorientat

[•devilkind]

imi pare rau ca fac un topic nou stiu ca mai era unu, insa l-am cautat o gramada fara sa il gasesc. Deci cum se face fluxul intrun graf neorientat??

[•Marius]

Cod:

C[i][j] = C[j][i] = c

Pentru toate perechile de noduri, mai putin sursa si destinatie, unde pui capacitatile in mod normal: de la sursa la un nod si de la un nod la destinatie. Si faci flux maxim.

[•devilkind]

ms mult. si scz ink o data ptr ca am creeat ink un topic.

[•Marius]

Incearca croco de la .campion 2006, runda 7!

[•pauldb]

Sau critice . La croco merge bine algoritmul din articolul nou  .

[•devilkind]

pai de fapt critice incerc sa rezolv akuma . ink o intrebare: dak am adaugat pe muchia x-y fluxul f ce se intampla cu muchia y-x??

[•pauldb]

Muchia Y-X fluxul scade cu F. Adica cresti fluxul, dar in sens opus. (Asta e valabil si la fluxul in graf orientat).

[•wefgef]

Fluxul intr-un graf neorientat merge exact la fel ca intr-un graf orientat. Nu trebuie sa modifici absolut nimic in codul tau (cel putin asa cum implementez eu fluxul nu trebuie ). Spor la treaba!

[•devilkind]

la implementarea mea trebuie modificat ptr ca la flux in graf orientat pe muchia inversa pun capacitate 0 , altfel risc sa vina fluxu invers, iar la flux in graf neorientat pe muchia inversa pun capacitate c.

PS: ink nu am inteles dinic si nu am gasit un articol bun despre edmond karp asa ca folosesc ink ford fulkerson

[•StTwister]

Edmonds-Karp e o generalizare a algoritmului Ford-Fulkerson care foloseste BFS pentru a gasi un drum de inaintare. Deci nu vad cum ai putea sa sti Ford-Fulkerson si sa nu sti Edmonds-Karp

[•Marius]

Pornesti din nodul sursa si faci o parcurgere in latime, BFS, si nu in adancime, DFS, cum zice Fulkerson.

[•devilkind]

da akuma am inteles. Mi-a explicat felix mai devreme (ms man). Eu nu stiam exact cum gasesc drumu dupa aceasta parcurgere.