


		

		EXCURSIE - SOLUTIE
	       --------------------

	Intai se calculeaza distantele minime de la fiecare oras la fiecare oras (Roy-Floyd
- in N^3). Apoi se construieste matricea A[i,p], cu semnificatia: costul platit daca in
saptamana p, Ion s-ar caza in orasul I. Asadar, A:[1..N,1..M].
A[i,P] = suma dublului distantelor de la i la fiecare oras care trebuie vizitat in fiecare
din cele 7 zile, plus costul cazarii in orasul i; daca orasul care trebuie vizitat intr-o
anumita zi este i, sau 0, atunci costul vizitarii acestuia va fi 0, si deci nu va contribui
la suma totala.
	Avand calculate toate elementele matricii A, trebuie sa determinam M orase,i1,i2,..,
iM, astfel incat suma A[i1,1]+A[i2,2]+..+A[iM,M] sa fie minima.
	Se aplica un algoritm de flux maxim de cost minim, pe graful bipartit, format din
orasele de la 1 la N in partea stanga, si de saptamanile de la 1 la M, in partea dreapta.
Se pun muchii intre fiecare oras si fiecare saptamana, de capacitate 1, si cost A[i,p], unde
(i,p) este muchia orientata care tocmai a fost adaugata grafului. Se aduga o sursa virtuala,
de la care se duc muchii orientate, de cost 0 si capacitate 1, la fiecare oras. Se adauga,
de asemena, o destinatie virtuala, spre care se duc muchii de la fiecare saptamana la ea,
de cost 0 si capacitate 1. Evident, fluxul maxim va fi minimul dintre M si N. Pentru a
determina in ce orase se va caza Ion in fiecare saptamana, se verifica muchiile (i,p), i=1,..,N
si p=1,..,M. Daca exista flux pe o astfel de muchie, atunci Ion se va caza in orasul i, in
saptamana P. Evident, vor exista fix min(M,N) muchii prin care trece flux, datorita capaci-
tatilor unitare ale fiecarei muchii.