•fluffy
|
|
« : Aprilie 01, 2004, 00:34:53 » |
|
Aici puteţi discuta despre problema Traseu.
|
|
|
Memorat
|
|
|
|
•ParrAzitU
Client obisnuit
Karma: 0
Deconectat
Mesaje: 73
|
|
« Răspunde #1 : Februarie 01, 2005, 18:45:05 » |
|
Nu prea ma descurc cu traseu numai pe 2 teste si ce am facut eu de mana acasa imi merge si nu gasesc nicicum greseala.. Nu-mi puteti arata sa zicem primul test de la traseu, m-ar ajuta f. mult
|
|
|
Memorat
|
I'll be smiling as I decompose - the reaper awaits us all.
|
|
|
•ParrAzitU
Client obisnuit
Karma: 0
Deconectat
Mesaje: 73
|
|
« Răspunde #2 : Februarie 06, 2005, 22:46:07 » |
|
Pls, haideti datimi testul 4 sau 5 de la traseu sa ma verific putin sa vad care e faza ca nu pot nicium trece de ele...
|
|
|
Memorat
|
I'll be smiling as I decompose - the reaper awaits us all.
|
|
|
•silviug
|
|
« Răspunde #3 : Februarie 07, 2005, 10:27:24 » |
|
Descrie un pic algoritmul.. poate acolo gresesti.. Teste eu nu am dar daca-mi spui ce faci poate putem trage concluzii folositoare.
Numa bine,
Silviu
|
|
|
Memorat
|
"Don't gain the world and lose your soul, wisdom is better than silver or gold." [Bob Marley - Jamaican reggae musician & singer (1945 - 1981)]
|
|
|
•domino
|
|
« Răspunde #4 : Februarie 07, 2005, 11:06:05 » |
|
Pls, haideti datimi testul 4 sau 5 de la traseu sa ma verific putin sa vad care e faza ca nu pot nicium trece de ele... Testul 4: 49 140 1 24 665 2 3 3573 2 6 213 2 14 279 2 25 2663 2 32 2896 2 43 994 3 15 1622 3 21 189 4 7 113 4 39 3419 4 47 4600 5 1 3867 6 24 1081 6 34 1429 6 35 4478 6 36 1770 6 42 1660 6 45 94 7 1 3383 7 23 144 7 40 2321 8 18 4544 8 21 4769 8 44 4083 9 11 2473 9 17 218 9 20 4507 10 5 1890 10 34 2580 11 7 2828 11 19 3783 11 25 610 12 32 2169 13 35 389 13 41 3419 14 34 1023 15 19 108 15 25 3337 15 34 1243 16 18 3915 17 6 4008 17 26 919 17 33 3577 17 34 2616 17 45 3580 18 28 1661 18 34 3684 19 25 3459 19 41 1364 20 4 3569 20 7 4491 20 13 3174 21 6 3243 21 37 2697 22 20 3114 22 43 2929 23 25 137 23 33 3283 23 34 24 24 14 619 24 16 4684 24 34 402 24 41 2642 24 46 3529 25 5 4073 25 7 1754 25 12 1500 25 44 953 25 45 771 25 47 4650 26 40 284 27 10 3811 27 23 3243 27 24 4370 27 26 3391 27 30 4060 27 49 1223 28 8 4030 28 29 496 29 22 4045 29 30 2867 29 48 2790 30 5 2025 30 15 4808 31 10 2826 32 26 4511 32 28 3204 32 31 155 33 16 546 33 43 2127 34 9 1825 34 39 4502 35 3 3034 35 4 200 35 7 4720 36 1 4911 36 32 2821 36 47 3676 37 46 2179 37 48 490 38 10 4999 38 11 1019 39 1 350 39 8 1167 39 18 508 40 17 824 40 21 132 40 49 1045 41 2 1728 41 27 4905 41 29 1035 41 30 4016 41 36 1087 41 43 4753 41 46 3122 42 3 2560 42 8 197 42 19 2208 42 34 4461 42 35 2478 43 18 2295 43 42 864 43 49 3456 44 9 4553 44 19 1357 45 10 1659 45 23 2942 45 26 3530 46 25 4358 46 48 4539 47 43 144 47 49 471 48 1 2542 48 11 2650 48 38 3862 49 13 672 49 18 805 49 19 4912 49 32 4051
Sper sa te ajute
|
|
|
Memorat
|
|
|
|
•ParrAzitU
Client obisnuit
Karma: 0
Deconectat
Mesaje: 73
|
|
« Răspunde #5 : Februarie 07, 2005, 15:24:36 » |
|
@domino : mersi @silviug : Poate e algoritmu, deci sa descriu pe scurt cum fac: iau nodurile care au gradul de intrare mai mare decat gradul de iesire si le leg de o sursa prin muchii de cap g_intare-g_iesire si cost 0. Apoi iau nodurile cu g_intrare<g_iesire si le leg de o destinatie tot asa prin muchii de cap diferenta si cost 0 si apoi intre nodurile astea pun muchii de cost dist minima in graful dat, intre noduri, si cap infinit. Si fac flux maxim de cost minim. No si pe toate drumurile de crestere adaug la rezultat(care e initial suma muchiilor din graf) cantitatea cu care am crescut fluxul * costul muchiei. Si cam atat.
|
|
|
Memorat
|
I'll be smiling as I decompose - the reaper awaits us all.
|
|
|
•silviug
|
|
« Răspunde #6 : Februarie 07, 2005, 17:19:13 » |
|
Algoritmul pare okay. E de la implementare. Good luck la debugat !
|
|
|
Memorat
|
"Don't gain the world and lose your soul, wisdom is better than silver or gold." [Bob Marley - Jamaican reggae musician & singer (1945 - 1981)]
|
|
|
•Cosmin
|
|
« Răspunde #7 : Februarie 07, 2005, 18:29:56 » |
|
Faina idee parazite
|
|
|
Memorat
|
|
|
|
•ParrAzitU
Client obisnuit
Karma: 0
Deconectat
Mesaje: 73
|
|
« Răspunde #8 : Februarie 07, 2005, 22:43:37 » |
|
Pai mio zis unu.. Pacat ca nu pot sa o fac de maxim..
|
|
|
Memorat
|
I'll be smiling as I decompose - the reaper awaits us all.
|
|
|
•silviug
|
|
« Răspunde #9 : Februarie 08, 2005, 01:46:46 » |
|
Cum implementezi flux cu costuri ?
|
|
|
Memorat
|
"Don't gain the world and lose your soul, wisdom is better than silver or gold." [Bob Marley - Jamaican reggae musician & singer (1945 - 1981)]
|
|
|
•ParrAzitU
Client obisnuit
Karma: 0
Deconectat
Mesaje: 73
|
|
« Răspunde #10 : Februarie 08, 2005, 08:47:43 » |
|
Pai dau la cost[i,j] = drumul minim de la i la j cost[j,i] = -cost[i,j] si apoi fac de fiecare data cand caut un drum de crestere a fluxului de cost minim cu un Roy-Floyd..
|
|
|
Memorat
|
I'll be smiling as I decompose - the reaper awaits us all.
|
|
|
•silviug
|
|
« Răspunde #11 : Februarie 08, 2005, 10:07:59 » |
|
Aham.. Personal fac cu Bellman-Ford. Nu am incercat niciodata varianta cu Roy-Floyd pentru ca are si complexitatea mai mare in general ( O(N^3) >= O(M*N) ).
|
|
|
Memorat
|
"Don't gain the world and lose your soul, wisdom is better than silver or gold." [Bob Marley - Jamaican reggae musician & singer (1945 - 1981)]
|
|
|
•ParrAzitU
Client obisnuit
Karma: 0
Deconectat
Mesaje: 73
|
|
« Răspunde #12 : Februarie 08, 2005, 10:40:43 » |
|
Pai scriu mai putin la roy-floyd si nu ma prea deranjeaza complexitatea la n<60.. oricum nu iau nici un tle..
|
|
|
Memorat
|
I'll be smiling as I decompose - the reaper awaits us all.
|
|
|
•LordAnta
Strain
Karma: 2
Deconectat
Mesaje: 43
|
|
« Răspunde #13 : Februarie 21, 2005, 20:22:46 » |
|
Stie cineva un algoritm mai bun de a gasi toate ciclurile disjuncte dintr-un graf, in afara de cel pe baza DF??? Am gasit o solutie prin adunarea tuturor ciclurilor dim graf!!! (Merge cateva teste, in rest TLE-uri!)
|
|
|
Memorat
|
Lord Anta, over and out!!!
|
|
|
•Cosmin
|
|
« Răspunde #14 : Februarie 21, 2005, 22:30:12 » |
|
Tu te referi la algoritmu de gasire a fluxului maxim de cost minim cu cycle canceling sau ce vrei exact sa zici?
|
|
|
Memorat
|
|
|
|
•LordAnta
Strain
Karma: 2
Deconectat
Mesaje: 43
|
|
« Răspunde #15 : Februarie 21, 2005, 22:38:34 » |
|
Nu, pur si simplu gasesc toate ciclurile(circuitele) din graf si adun costurile lor. Merge, dar trebuie optimizat codul de gasire a ciclurilor!!!
|
|
|
Memorat
|
Lord Anta, over and out!!!
|
|
|
•cavendish
Strain
Karma: 2
Deconectat
Mesaje: 43
|
|
« Răspunde #16 : Februarie 21, 2005, 23:02:35 » |
|
Nu cred ca merge asa. Chiar daca gasesti toate ciclurile, nu poti doar sa le aduni. Mai e vorba si de drumul de la un ciclu la altul (la urma urmei, totul e un drum lung prin graf) (nu te baza pe exemplu, care e un caz particular). Si din cauza drumuilui astuia cred ca solutia propusa mai sus e singura implementabila. Mai ii backtrackingu . Oricum, misto problema. Pacat ca nu mi-am dat seama singur de rezolvare
|
|
|
Memorat
|
|
|
|
•the_godfather
Strain
Karma: -6
Deconectat
Mesaje: 26
|
|
« Răspunde #17 : Februarie 12, 2006, 17:27:12 » |
|
Imi spune si mie cineva ce am gresit. Algoritmul meu mi se pare corect chiar daca e O(N^3). Calculez drumul minim intre toate nodurile grafului cu roy-floyd, iar apoi drumul de cost minim pornind din nodul 1 este : for(i=1;i<n;i++) s+=a[i][i+1]; //drumul de la nodul 1 la 2; de la 2 la 3 etc. n-1...n s+=a[n][1] //drumul de la nodul n la nodul 1 Pentru testul asta de aici (4) imi da un drum mai mic 323963.
Imi explica si mie cineva va rog ce gresesc?PLS ](*,) Multumes anticipat! [-o<
|
|
|
Memorat
|
|
|
|
u-92
Vizitator
|
|
« Răspunde #18 : Februarie 12, 2006, 17:28:41 » |
|
ai citit macar posturile de mai sus?
|
|
|
Memorat
|
|
|
|
•alex_prg
Strain
Karma: -5
Deconectat
Mesaje: 21
|
|
« Răspunde #19 : Aprilie 13, 2006, 22:42:18 » |
|
repet si io ... faina ideea de rezolvare. Asta e solutia oficiala a problemei ?
|
|
|
Memorat
|
reality is just an illusion created by the lack of alcohol
|
|
|
•darius.crisan
Strain
Karma: 0
Deconectat
Mesaje: 1
|
|
« Răspunde #20 : Ianuarie 21, 2016, 17:26:48 » |
|
Poate sa-mi trimita si mie cineva rezolvarea in Pascal? Nu o gasesc nici cum prin surse. Nu inteleg nici modul de rezolvare.
|
|
|
Memorat
|
|
|
|
|