Tero

Dupa cum multi si-au dat seama, problema este asemanatoare cu cea a lui Dan Ionut Fechete, Trafic.

Fiind niste limite de timp foarte mari, cautare binara + flux nu intra in timp.

Pentru a se incadra in limita stabilita, era necesar algoritmul lui Karzanov pentru flux maxim intr-o retea. Acest algoritm a fost prezentat in cadrul taberei de pregatire a Lotului National, de catre Mugurel Ionut Andreica (Algoritmi de flux maxim in retele) si constituie o mica parte din teza sa de Masterat.

Presupunem, intial, ca pe fiecare muchie poate fi plasat doar un singur soldat. Cum S < M, acest lucru este intotdeauna posibil. Astel, fiecarei muchii i se va atribui capacitatea 1. Rulam algoritmul de flux maxim si retinem fluxul. Calculam, pentru fiecare muchie, maximul dintre distantele de la aceasta pana la nodul 1 si pana la nodul N, apoi sortam descrescator muchiile, in functie de aceasta valoare.
In continuare, vom incerca sa gasim pozitia soldatului care ajunge ultimul in orasul atacat, parcurgand muchiile in ordinea sortarii: pentru o muchie e, vrem sa stabilim daca, pozitionand mai mult de un soldat pe ea (crescand capacitatea la o valoare foarte mare), va creste sau nu fluxul initial. Daca nu va modifica valoarea fluxului, inseamna ca putem pune oricati soldati pe e, fara a influenta rezultatul final, deci muchia este inutila. Daca modifica valoarea fluxului, asta inseamna ca cel mai lenes soldat trebuie sa fie pozitionat pe e si afisez valoarea maximului dintre distante pentru muchia respectiva.

Pentru a avea o complexitate teoretica de O(M*N3) (in practica merge cu mult mai repede), va trebui sa facem doua optimizari:

  1. se va reface reteaua reziduala L0 (vezi articolul lui Mugurel) doar daca exista un drum nesaturat, ce contine muchia e
  2. pentru a verifica daca fluxul creste, nu se va relua tot algoritmul de flux maxim, ci se vor folosi informatiile anterior calculate.

Desi nu ar fi trebuit sa ia decat 30 de puncte, in solutia prezentata de Ionut Fechete, se putea inlocui Edmond-Karp cu algoritmul lui Dinic (vezi articolul lui Mugurel), obtinandu-se astfel punctaj maxim. Singurul care a facut acest lucru in concrus (si singurul care a obtinut punctaj foarte mare la aceasta problema), a fost Bogdan Tataroiu.

In arhiva vom incerca sa schimbam testele astfel incat aceasta solutie sa nu obtina punctaj maxim.