nave-bunicu-hint1

Hint 1

Scrie aici despre nave-bunicu-hint1

Cum putem transforma problema intr-una de flux maxim de cost minim?
 
Exista mai multe abordari aici, dar cea cu cele mai putine muchii si cu costuri relativ simple ar fi urmatoarea:
 
* Pentru fiecare valoare posibila $X$ un nod $X$.
* Un nod sursa $S$ si unul destinatie $D$.
* Muchie intre $X$ si $X+1$ bidirectionala de capacitate infinit si cost $1$.
* Muchie intre $S$ si $X$ (merge doar unidirectionala) cu capacitate numarul de aparitii a lui $X$ in sir-ul original.
* Muchie intre $X$ si $D$ (merge doar unidirectionala) cu capacitate 1 (in cazul lui nave ordonate/ordonare), dar ar putea fi si $K$ daca problema ne lasa sa avem $K$ cu aceeasi valoare.