infoarena

infoarena - concursuri, probleme, evaluator, articole => UVA => Subiect creat de: Ionescu Vlad din Ianuarie 01, 2008, 18:52:00



Titlul: 10806 - Dijkstra, Dijkstra.
Scris de: Ionescu Vlad din Ianuarie 01, 2008, 18:52:00
http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=20&page=show_problem&problem=1747

Iau WA. Pe toate testele pe care le pot verifica manual (sau cu back; ar fi culmea ca si backu sa dea *acelasi* raspuns gresit) imi da bine. Aveti niste teste sau idei ce ar putea avea?

Eu gasesc un drum minim, fac niste transformari pe graf, mai gasesc un drum minim, iar apoi prelucrez drumurile gasite...


Titlul: Răspuns: 10806 - Dijkstra, Dijkstra.
Scris de: Paul-Dan Baltescu din Ianuarie 01, 2008, 19:16:25
Pe urmatorul exemplu:

4 5
1 2 1
2 3 1
3 4 1
1 3 2
2 4 2

daca initial alegi drumul minim 1-2-3-4, iti mai merge rezolvarea? :)



Titlul: Răspuns: 10806 - Dijkstra, Dijkstra.
Scris de: Ionescu Vlad din Ianuarie 01, 2008, 19:23:25
Nu m-am uitat ce drum aleg (ar fi mai dificila reconstituirea..), dar imi da 6, atat cu rezolvarea eficienta cat si cu back. Nu e bine 6?


Titlul: Răspuns: 10806 - Dijkstra, Dijkstra.
Scris de: Paul-Dan Baltescu din Ianuarie 01, 2008, 19:59:17
E bine 6. Problema e ce drum alegi initial. Daca alegi 1-2-4 sau 1-3-4 initial, la pasul 2 ii poti alege perechea. Daca alegi 1-2-3-4 initial, nu vei mai avea drum pentru pasul 2. Algoritmul de drum minim nu iti garanteaza ce drum alegi initial. Intamplator, pe testul pe care ti l-am dat il alegeai bine. Incearca si testul asta:

4 5
1 2 1
2 3 1
3 4 1
1 3 3
2 4 3

Trebuie sa dea 8.


Titlul: Răspuns: 10806 - Dijkstra, Dijkstra.
Scris de: Ionescu Vlad din Ianuarie 01, 2008, 20:21:45
Pai eu nu fac pur si simplu drum initial + eliminare muchii + inca un drum. Am zis ca fac unele modificari pe graf si pe acest drum. Pe exemplu imi da 8.

Cat despre algoritm, mai pe larg e cam asa:

Gaseste un drum minim de la 1 la n.
Toate muchiile le inlocuiesc cu arce orientate catre sursa (mai exact, daca drumul e format din muchiile (1,2), (2,3), acestea vor fi inlocuite cu arcele 2->1 si 3->2). Costul acestor arce il pun pe -1.
Rulez din nou algoritmul de drum minim (eu am ales bellman ford sa n-am probleme cu costurile negative..). Apoi elimin muchiile alese atat in primul drum cat si in cel de-al doilea, si imi raman muchiile drumului dus-intors.

Edit: Alte idei de rezolvare care ar fi? Am inteles ca se poate face si cu flux?


Titlul: Răspuns: 10806 - Dijkstra, Dijkstra.
Scris de: Paul-Dan Baltescu din Ianuarie 01, 2008, 21:45:13
Contraexemplu:
4
6
1 2 4
2 3 4
3 4 4
1 3 9
2 4 9
1 4 16

Tie iti da 28, raspunsul este 26. :)

Problema se rezolva cu flux. Tu faci ceva asemanator, mai putin ca arcele de intoarcere le faci -1 si nu -cost. :)


Titlul: Răspuns: 10806 - Dijkstra, Dijkstra.
Scris de: Ionescu Vlad din Ianuarie 01, 2008, 21:51:10
 [-o<
Nu m-as fi gandit la asta :). Mersi mult, am luat accepted. :)