infoarena

Cum se rezolva ?

Ce probleme stiti care se rezolva cu acest algoritm ?

Multumesc anticipat!

inmultesti cu -1 muchiile si faci flux maxim de cost minim.

Eu zic ca problema de flux maxim si cost maxim e NP hard, pentru ca in final se reduce tot la gasirea unui drum de cost maxim de la sursa la destinatie. Inmultirea asta cu -1 pentru a afla un drum de cost maxim intre doua noduri cred ca nu functioneaza din urmatoarele motive: sa presupunem ca toate muchiile au cost pozitiv, graful contine cicluri ( daca nu, problema se rezolva cu complexitate liniara ) si este conex. Cand facem costurile negative sigur exista un ciclu de cost negativ in care se poate ajunge din nodul de start, si acest ciclu am putea sa il parcurgem la infinit obtinand un cost mai mic.

da, asa e :oops:

Aceeasi idee am avut-o si eu. -1 amandoi :)

Dar in schimb cuplaj maxim de cost maxim, cand muchiile au cost pozitiv, merge.

Cam tarziu vine si raspunsul meu...

Ideea mea e ca in loc sa inmultesti costurile cu -1 sa le scazi dintr-o constanta mare (INFINIT), adik c[j] = INF - c[j]

Astfel se inverseaza relatia de ordine dintre costuri, si raman si pozitive in acelasi timp, adica nu exista cicluri de cost negativ. Si se face fluxu de cost minim pe noua retea.

Nu am testat, dar cred ca ar merge.

Astept contraexmple :P

Nu e corect, de exemplu ai un graf orientat cu 3 noduri si muchiile 1->2, 2->3, 1->3.
1 e sursa, 3 e destinatia, ai capacitatea 1 pe fiecare muchie si costurile 1->2: 5, 2->3: 6, 1->3: 9
Noile costuri vor fi INF-5, INF-6 si INF-9 iar tot timpul 2*INF-11 > INF-9 (pt INF destul de mare, mai mare decat 3), deci iti va gasi drumul 1->3 ca fiind de cost maxim.

Si totusi cum se face cuplajul de cost maxim?

Consideri Vmax = cel mai care cost al unei muchii si pentru fiecare muchie faci transformarea cost[muchie] = Vmax-cost[muchie]. Acum costul minim o sa fie <valoare cuplaj>*Vmax-(suma costurilor muchiilor initiale din cuplaj) => suma costurilor muchiilor initiale din cuplaj e maxima.