dDve sela mogu da komuniciraju sa satelitskom antenima ako obe sela imaju antene, ili dovoljno je da edno od nih ima?
Teks zadatka govori da obe moraju imati, al test primer pokazuje sasvim suprotno.
Ne bih rekao da test primer pokazuje suprotno. Mozes li da pojasnis zasto mislis da pokazuje suprotno? Potrebno je da oba sela imaju, kao sto je i navedeno.
E pa ovako. Kad podredim rastojanja u opadajuci redosled, rezultat je petti (od ukupno 6 otsecka) Znaci, sa ove 2 antene treba d apokrijem ukupno 4 otsecka, a nezavisno kako i da bi bili postavljeno, 4 otsecke imaju vise nego 2 krajne tocke ukupno, tako da ne bih mogao da pokrijem sve te sa 2 satelitske
Ali tebi svaki grad ima nacin da se poveze sa drugim gradom bez ikakvih satelita. Ti ne moras da imas ijedan satelit. Hajde napisi kako ti povezujes gradove, tacno sa duzinama, jer mozda nisi shvatio sta se trazi, pa da pojasnim. Da povezes n gradova, tebi treba najvise n-1 odsecak.
Da podredimo rastojanja u opadajuci redolsed, dobijamo sledeca lista rastojanja i redni nrojeva sela koi su njihovi krajne tacke:
1 4 667.083
1 3 500
2 4 474.342
2 3 300
3 4 212.132
1 2 200
Sad vidim da resenje je rastojanje megu sela 3 i 4, a to mora da znaci da 1 i 4 mogu da komuniciraju sa satelitom, 1 i 3 takodzer, a 2 i 4; 2i 3 isto komuniciraju preko satelitom. To znaci da 3 i 4; i 1 i 2; (; za da razdvojim parove) komuniciraju radiom, pa zato rezultat je rastojanje megu 3 i 4. (ovo je razmisljanje backwards, kad vidim rezultat)
Sad pitanje je, kako s a 2 satelitski antenama mogu da budu povezani 1i 4; 1 i 3; 2 i 4; 2 i 3? Gde su satelitske antene i kako rade?
E ovako, recimo da povezes
grad 1 i grad 2
grad 2 i grad 3
grad 3 i grad 4
Na ovaj nacin si povezao sve gradove i oni mogu da komuniciraju (neki direktno, neki preko ostalih), samo sto ti d mora biti 300. E sad, ako bi u grad 2 i grad 3 stavio satelite, onda ovu velicinu od 300 izbacis i ostaje ti da je d 212.132
Ti nema potrebe da povezujes 1i 4; 1 i 3; 2 i 4; 2 i 3. Recimo da si povezao 1i 4; 1 i 3; 2 i 4;, tada su ti 2 i 3 povezani na sledeci nacin 2 -> 4 -> 1 -> 3.
Jel' sad ok?
Ok, fala, mislim da sam razumeo
Znaci, razmisljanje je bio ovako: treba mi najmanje n-1 odsecaka tako da svi sela bude povezani => MCST
Ondak svi otsecaka koi ucestvuvaju sortiram po duzine i radim greedy, ono sto bi bio najnormalno, rasporedim antene na krajeve najduze otsecke dok ne ih potrosim i prva otsecka koja ne ulazi je rjenje. Proslo samo na prvi, ondak am procita thread i asm uradio spored tijaninu ideju i sve je proslo. Zasto?
Pa ideja je ok, samo ti za izbegavanje k odsecaka, treba da imas k + 1 antenu, a ne 2*k ili tako nesto... Moguce da nisi bas najbolje shvatio oko rasporeda antena ili ja tebe nisam shvatio :)
Ako ti je lakse, mozes dati neki test primer.
Mislim na ovo, posle kreiranje MCST, ja sam sortirao svi te otsecke u opadujuci redosled i sam poceo rasporedjivati antene na njihovi krajeve dok ne ih svi potrosim. Prva otsecka koja nema antena na bar jedan kraj je rijesenje, ali ovo nije radilo.
To sto je radilo je , ako imam a antena, rijesenje je a-ti clan soriranog nizu otsecka koji ucestvuvaju u MCST. Zasto? Kako mi so sigurnost znamo da a antene mogu da pokrije ove prve a-1 otsecka? Recimo, ako imam 3 antene, a u MCST najveci 3 otsecka nisu susedne, rijesenje je vtora (druga) otsecka po vecina, a ne a-ta (sta u ovom slucaju znaci treca)
