|
Titlul: 031 Traseu Scris de: Dan-Leonard Crestez din Aprilie 01, 2004, 00:34:53 Aici puteţi discuta despre problema Traseu (http://infoarena.ro/problema/traseu).
Titlul: 031 Traseu Scris de: Bindea Calin din Februarie 01, 2005, 18:45:05 :oops: 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 :)
Titlul: 031 Traseu Scris de: Bindea Calin din 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...
:oops: Titlul: 031 Traseu Scris de: Silviu-Ionut Ganceanu din 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 Titlul: 031 Traseu Scris de: Mircea Pasoi din Februarie 07, 2005, 11:06:05 Citat din mesajul lui: ParrAzitU 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... :oops: Testul 4: Cod: 49 140 Cod: 529092 Sper sa te ajute :) Titlul: 031 Traseu Scris de: Bindea Calin din Februarie 07, 2005, 15:24:36 @domino : mersi :P
@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. :roll: Titlul: 031 Traseu Scris de: Silviu-Ionut Ganceanu din Februarie 07, 2005, 17:19:13 Algoritmul pare okay. E de la implementare. Good luck la debugat :D!
Titlul: 031 Traseu Scris de: Cosmin Negruseri din Februarie 07, 2005, 18:29:56 Faina idee parazite ;)
Titlul: 031 Traseu Scris de: Bindea Calin din Februarie 07, 2005, 22:43:37 :P Pai mio zis unu.. ;) Pacat ca nu pot sa o fac de maxim.. :(
Titlul: 031 Traseu Scris de: Silviu-Ionut Ganceanu din Februarie 08, 2005, 01:46:46 Cum implementezi flux cu costuri ?
Titlul: 031 Traseu Scris de: Bindea Calin din 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.. :roll: Titlul: 031 Traseu Scris de: Silviu-Ionut Ganceanu din 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) ).
Titlul: 031 Traseu Scris de: Bindea Calin din 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.. :?
Titlul: 031 Traseu Scris de: Anton Alexandru din 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!)
Titlul: 031 Traseu Scris de: Cosmin Negruseri din 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?
Titlul: 031 Traseu Scris de: Anton Alexandru din 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!!!
Titlul: 031 Traseu Scris de: Dima Alex din 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 :roll:
Titlul: 031 Traseu Scris de: Iacob Ioan Fanica din 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 :
Cod:
Titlul: 031 Traseu Scris de: u-92 din Februarie 12, 2006, 17:28:41 ai citit macar posturile de mai sus? :)
Titlul: Raspuns: 031 Traseu Scris de: Prigoana Alexandru din Aprilie 13, 2006, 22:42:18 repet si io ... faina ideea de rezolvare. Asta e solutia oficiala a problemei ?
Titlul: Răspuns: 031 Traseu Scris de: Darius Crisan din 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.
|