Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 10806 - Dijkstra, Dijkstra.  (Citit de 7425 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
Dastas
Vorbaret
****

Karma: 11
Deconectat Deconectat

Mesaje: 170



Vezi Profilul
« : 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...
Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #1 : 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? Smile

Memorat

Am zis Mr. Green
Dastas
Vorbaret
****

Karma: 11
Deconectat Deconectat

Mesaje: 170



Vezi Profilul
« Răspunde #2 : 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?
Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #3 : 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.
Memorat

Am zis Mr. Green
Dastas
Vorbaret
****

Karma: 11
Deconectat Deconectat

Mesaje: 170



Vezi Profilul
« Răspunde #4 : 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?
« Ultima modificare: Ianuarie 01, 2008, 20:59:12 de către Ionescu Vlad » Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #5 : 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. Smile

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

Am zis Mr. Green
Dastas
Vorbaret
****

Karma: 11
Deconectat Deconectat

Mesaje: 170



Vezi Profilul
« Răspunde #6 : Ianuarie 01, 2008, 21:51:10 »

 Pray
Nu m-as fi gandit la asta Smile. Mersi mult, am luat accepted. Smile
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines