h2. "Negot":https://infoarena.ro/problema/negot
Aceasta este o aplicatie de flux maxim, insa exista o solutie care se misca mai bine folosind cuplaj maxim in graf bipartit.

Pentru flux: vom crea un nod 0 sursa si N muchii de capacitate K de la sursa la producatori. Toate muchiile de la producator la magazin au capacitate 1. Vom crea, de altfel, si un nod destinatie si M muchii de capacitate 1 de la magazine la destinatie.

Pentru flux: vom crea un nod 0 sursa si vom crea N muchii de capacitate K. Toate muchiile de la producator la magazin au capacitate 1. Vom crea, de altfel, si un nod destinatie si M muchii de capacitate 1 de la magazine la destinatie.

Pentru cuplaj: putem "clona" un producator de K ori si fiecare clona sa o cuplam cu maxim 1 magazin. Restrictiile permit crearea efectiva a N*K noduri cu tot cu muchiile aferente, insa pentru o solutie performanta vom tine un vector de aparitii al fiecarui nod dintre cele N. Frecventa petru fiecare nod nu trebuie sa fie mai mare decat K in timp ce cuplam.

protected

public