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.
