Mucim se s ovim zadatkom vec duze vreme...
Ovako ide moj algoritam:
Krenem od prvog sela i nadjem njemu najblizi. Zatim nadjem najblize selo za ova dva i tako n-1 puta. Znaci ovo je Primov algoritam, s tim sto ovde za svaku novu duzinu koju nadjem (ivicu grafa) pamtim duzinu kao i njene krajeve (cvorove grafa). Onda te duzine sortiram u nerastucem poretku i na svaku redom postavljam antene koliko ih ima. Ako strignem do neke duzine gde su sve antene iskoriscene i bar jedno selo nema satelitsku antenu, tu stajem i ispisujem tu duzinu.
Meni se cinilo da ovo radi, al' ispalo je da prolazi samo za prvi primer, a za ostale ispisuje pogresno resenje.
Jeste li vi ovako radili? Zna li ko moze li stogod da se ispravi, pa da ovo proradi?
Ovako ide moj algoritam:
Krenem od prvog sela i nadjem njemu najblizi. Zatim nadjem najblize selo za ova dva i tako n-1 puta. Znaci ovo je Primov algoritam, s tim sto ovde za svaku novu duzinu koju nadjem (ivicu grafa) pamtim duzinu kao i njene krajeve (cvorove grafa). Onda te duzine sortiram u nerastucem poretku i na svaku redom postavljam antene koliko ih ima. Ako strignem do neke duzine gde su sve antene iskoriscene i bar jedno selo nema satelitsku antenu, tu stajem i ispisujem tu duzinu.
Meni se cinilo da ovo radi, al' ispalo je da prolazi samo za prvi primer, a za ostale ispisuje pogresno resenje.
Jeste li vi ovako radili? Zna li ko moze li stogod da se ispravi, pa da ovo proradi?