699 Online

[•astronomy]

Aici puteţi discuta despre problema Online.

[•anouk]

help much needed...
Am implementat un Kruskal pt determinarea costului initial apoi pt celelalte K muchii, daca nu erau deja in APM, am verificat care este muchia cu costul maxim din ciclul format, si daca era cazul, o scoteam din lista si o adaugam pe cea noua. Am incercat si pe cateva teste de-ale mele si mi-a dat bine, pur si simplu nu-mi dau seama de ce iau doar 10 puncte. Am vreo greseala in gandire sau imi scapa vreun caz? De precizat ca muchiile pe care le scot din lista nu le sterg din lista, ci le setez ca de nefolosit.

[•fireatmyself]

incearca urmatorul test

Cod:

7 6
1 2 2
1 3 2
3 7 2
2 4 2
4 5 3
4 6 3
8
2 7 1
3 7 3
1 7 1
4 2 1
6 7 4
6 7 1
5 6 3
5 7 1

raspunsul ar trebui sa fie:

Cod:

14
13
13
12
11
11
9
9
7

sper sa nu fi gresit

[•anouk]

asa primesc si eu
off.. problema asta imi mananca nervii

[•fireatmyself]

Cod:

10 10
1 3 3
1 2 3
3 5 1
3 8 1
5 8 2
5 4 1
5 6 1
5 7 1
8 9 1
8 10 1
8
2 3 4
2 3 1
3 2 1
4 5 6
5 4 1
4 5 7
8 6 3
2 10 1

Cod:

13
13
11
11
11
11
11
11
11

Cod:

10 10
1 3 4
1 2 4
3 5 1
3 8 1
5 8 2
5 4 1
5 6 1
5 7 1
8 9 1
8 10 1
7
2 3 3
1 3 4
2 5 4
2 3 1
2 3 2
6 7 1
7 3 1

Cod:

15
14
14
14
12
12
12
12

[•anouk]

tot aceleasi rezultate 
acum sunt sigura ca gresesc undeva din neatentie

[•tm_radu]

Trimite-mi daca vrei un mail cu sursa sa ma uit peste ea.

[•marcelcodrea]

Imi poate spune cineva ce rezultat primeste pentru testul :

Cod:

9 11
5 6 10
1 2 3
6 9 12
8 9 7
3 6 5
2 7 4
8 2 20
3 1 5
8 5 13
4 3 5
6 7 4
9
1 2 1
2 3 1
3 6 3
1 7 3
2 6 2
3 6 4
8 9 8
1 4 1
3 6 1

Va multumesc anticipat !

[•pauldb]

Cod:

50
48
44
43
42
41
41
41
37
36

[•MciprianM]

Cum putem sorta muchiile dupa cost folosind sort din stl?
Folosesc o structura de genul:

Cod:

struct muchie{
  int n1,n2,cost;
};

pentru a memora muchiile.

[•bogdan2412]

Definesti o functie de comparare:

Cod:

int cmp(muchie a, muchie b)
{
    return a.cost < b.cost;
}

pe care o dai ca parametru la sort.

Cod:

sort(v.begin(), v.end(), cmp);

Asa sortezi un vector v cu elemente de tip muchie, crescator dupa cost.

[•MciprianM]

ms.

[•Addy.]

cum fac sa gasesc ciclul format (muchiile care il compun)?
banuiesc ca e ceva cu DFS, dar chiar nu ma prind acum..

[•pauldb]

Nu e nevoie sa-l gasesti. Poti aplica un algoritm de APM la fiecare pas. Dupa ce determini APM-ul initial, la fiecare pas vei avea doar N muchii candidat.

[•Addy.]

multumesc pentru ajutor! m-am lamurit cu asta, dar acum nu reusesc sa iau deloc puncte, desi m-am verificat si eu si imi dau bine si toate testele puse pe forum. este vreo smecherie?

[•avram_florin]

Nu inteleg de ce iau decat 10 puncte!Primesc Killed by signal 11(SIGSEGV) care din cate stiu e se refera la depasirea memoriei,dar totusi tot ce declar

const int MaxN = 201;
struct muchie{
      int x,y,cost;
      };
vector<muchie> e,E;
int N,M,K,Cost,Lg,T[MaxN],rg[MaxN];
 si cateva variabile locale.Imi poate explica si mie cineva de ce tot primesc sigsegv.

[•pauldb]

Mai probabil primesti SIGSEGV din cauza ca depasesti limitele unui vector.