805 Gminmax

[•wefgef]

Aici puteti discuta despre problema Gminmax.

[•Mishu91]

Am rezolvat problema folosind arbori de intervale, dar solutia cu N liste nu am prea inteles-o. Ce tin defapt in acele liste si cum le actualizez la fiecare pas. Puteti detalia putin, va rog

[•gcosmin]

Am modificat. Sper ca acum se intelege mai bine

[•Mishu91]

Mersi

[•Robytzza]

e ceva special cu testu 7?

[•DraStiK]

Am o întrebare, asupra unei soluții alternative:

Țin un heap ordonat după gradele nodurilor, și la fiecare pas scos din heap nodul cu grad minim, ii actualizez vecinii, si apoi verific dacă gradul nodului din vârful heap-ului este o îmbunatățire a soluției.

Este greșită soluția asta?

[•Mishu91]

Ai grijă să refaci heap-ul pentru fiecare vecin actualizat. Dacă folosești priority_queue sau heap din STL nu va merge treaba.

[•DraStiK]

Poți sa îmi explici mai pe larg de ce priority_queue din STL nu merge?

Chiar îmi place structura asta. Și chiar vroiam sa întreb cum exact își face update-ul.

[•Mishu91]

Ideea este că el își face update-ul doar dacă inserezi un element, dar dacă modifici valorile heapul nu se va reface, iar vârful heapului nu este garantat cel mai mic element. Sper să nu greșesc.

[•avram_florin]

imi poate spune si mie cineva ce e gresit in rezolvarea mea.

Cod:

for( i = 1 ; i <= N ; i++ )
		update(1,1,N,i,gr[ i ]);
	int nod,grmax,noduri,nrn;
	noduri = N;
	grmax = Arb[1].grad;
	nrn = N;
	while( noduri-- )
		{
			nod = Arb[1].nod;
			update(1,1,N,nod,INF);
			if( Arb[1].grad > grmax )
				{
					grmax = Arb[1].grad;
					nrn = noduri;
				}
			vector<int>::iterator it;
			for( it = G[nod].begin() ; it != G[nod].end() ; ++it )
				update(1,1,N,*it,--gr[*it]);
		}
	printf("%d %d\n" , grmax , nrn );

Foloseste tagul [ code ] ... [ / code ]

[•Kira96]

http://www.infoarena.ro/job_detail/1281129

"user.cpp:65:21: warning: unused variable ‘c***t’ [-Wunused-variable]"

Asa se vorbeste? 

[•patrutoiuandrei]

a luat cineva 100 pct cu solutia cu heapuri? eu am implementat manual si am MlogN dar iau tle pe 4 teste