Revizia anterioară Revizia următoare
Scurta descriere a unei solutii O(N logN) la problemele Nave
In sursa aceasta am rezumat felul in care arata reteaua de flux pe care o descrie, de fapt, problema. Imaginea se afla intre liniile 164 si 173. Faptul ca o retea de flux maxim de cost minim modeleaza cerinta inseamna ca indeplinim conditiile de convexitate cerute de cele ce urmeaza:
--- Indiciul 1
---
Prin urmare, cautam binar cel mai mare lambda pentru care numarul minim (notat cu cnt) de unitati de flux trimise direct la Destinatie, intr-o solutie de cost minim, este mai mic sau egal cu acel numar K dat. Problema se poate rezolva intr-un mod asemanator si daca am vrea sa-l maximizam pe cnt si sa facem cautarea binara putin pe dos, si puteti studia diferentele intre cele doua surse.
--- Indiciul 2
---
Vom folosi programare dinamica si vom avea grija sa obtinem, in caz de egalitate dupa cost, numarul minim de unitati de flux.
--- Indiciul 3
--- Indiciul 4
---
---
