Vizualizare soluţie
Titlul problemei: | trafic |
Numărul problemei: | 2 |
Runda: | |
Soluţie: | Pentru inceput vom calcula drumul minim de la nodul 1 la toate orasele si de la nodul n la toate orasele
utilizand orice algoritm de aflare a drumului minim.
Apoi vom utiliza metoda cautarii binare pentru a afla rezultatul. Avand un timp T fixat putem vedea daca exista o aranjare a soldatilor astfel incat distanta maxima la oricare din cele 2 capitale este <= T cu ajutorul algoritmului de flux maxim Pentru fiecare muchie putem afla daca un soldat poate fi plasat pe acea muchie sau nu. Daca sunt neclaritati se pot clarifica prin vizualizarea sursei. Acele muchii vor avea capacitatea 1 iar restul capacitatea infinit adica un numar considerabil de mare.Face acest lucru pentru a garanta ca taietura minima va contine doar muchii in care putem pune soldati. Exista o aranjare a soldatilor cu distanta maxima T daca si numai daca fluxul maxim este mai mic decat numarul de soldati.
Pentru fiecare test de evaluare s-au acordat 5 puncte.
|