031 Traseu

[•fluffy]

Aici puteţi discuta despre problema Traseu.

[•ParrAzitU]

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  

[•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...
 

[•silviug]

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

[•domino]

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:

Cod:

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

Cod:

529092

Sper sa te ajute

[•ParrAzitU]

@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.  

[•silviug]

Algoritmul pare okay. E de la implementare. Good luck la debugat !

[•Cosmin]

Faina idee parazite

[•ParrAzitU]

 Pai mio zis unu.. Pacat ca nu pot sa o fac de maxim..  

[•silviug]

Cum implementezi flux cu costuri ?

[•ParrAzitU]

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..  

[•silviug]

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) ).

[•ParrAzitU]

Pai scriu mai putin la roy-floyd si nu ma prea deranjeaza complexitatea la n<60.. oricum nu iau nici un tle..  

[•LordAnta]

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!)

[•Cosmin]

Tu te referi la algoritmu de gasire a fluxului maxim de cost minim cu cycle canceling sau ce vrei exact sa zici?

[•LordAnta]

Nu, pur si simplu gasesc toate ciclurile(circuitele) din graf si adun costurile lor. Merge, dar trebuie optimizat codul de gasire a ciclurilor!!!

[•cavendish]

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  

[•the_godfather]

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:

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< 

[u-92]

ai citit macar posturile de mai sus?  

[•alex_prg]

repet si io ... faina ideea de rezolvare. Asta e solutia oficiala a problemei ?

[•darius.crisan]

Poate sa-mi trimita si mie cineva rezolvarea in Pascal? Nu o gasesc nici cum prin surse. Nu inteleg nici modul de rezolvare.