h3. Explicaţie

...

Dupa ce parcurgem fiecare drum si incrementam cu 1 muchiile, valorile acestora sunt:
muchia 1 (5 -> 4): 9
muchia 2 (4 -> 2): 5
muchia 3 (3 -> 1): 5
muchia 4 (4 -> 6): 5
muchia 5 (1 -> 5): 8
 
Dupa normalizare, muchiile au valorile:
muchia 1 (5 -> 4): 0
muchia 2 (4 -> 2): 2
muchia 3 (3 -> 1): 3
muchia 4 (4 -> 6): 4
muchia 5 (1 -> 5): 1
 
Dupa inmultirea cu $alfa$, muchiile au valorile finale:
muchia 1 (5 -> 4): (0 * 7574) % 100003 = 0
muchia 2 (4 -> 2): (2 * 1) % 100003 = 2
muchia 3 (3 -> 1): (3 * 66670) % 100003 = 4
muchia 4 (4 -> 6): (4 * 25002) % 100003 = 5
muchia 5 (1 -> 5): (1 * 2) % 100003 = 2
 
Permutarea optima este: 4 5 2 1 6 3
<tex> \sum_{i=1}^{N} dist(i, p(i)) = 2 + 2 + 4 + 2 + 2 + 4 = 16</tex> si este maxima
Sirul de perechi este: { ({0, 2}, 4) , ({0, 2}, 5) , ({2, 0, 2, 4}, 2) , ({2, 0}, 1) , ({5, 0}, 6) , ({4, 2, 0, 5}, 3) }

== include(page="template/taskfooter" task_id="dedicatie") ==