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.

Înapoi

© 2002 - 2012. Realizat de Liviu Vâlsan. Administrat de Vlad Manea   XHTML   CSS