[ sannyy @ 01.02.2011. 21:53 ] @
U nekom naselju koje ima N zgrada potrebno je uvesti telefonsku mrežu. Za svaku od N zgrada poznate su x i
y koordinata lokacije na mapi na kojoj se zgrada nalazi. Potrebno je projektovati takvu funkcionalnu mrežu
telefonskih kablova da se za povezivanje zgrada potroši što je god moguće manje kabla. Mreža je
funkcionalna ukoliko postoji kablovska veza između svake dvije zgrade, koja ne mora nužno biti direktna,
nego može prolaziti i kroz druge zgrade. Kablovi se prostiru pravolinijski (tj. najkraćim putem) od zgrade do
zgrade, a jedine tačke u kojima se kablovi mogu međusobno vezati u mrežu (tj. jedine tačke u kojima se
mreža kablova razgranava) jesu upravo zgrade.

Code:
1: #include <fstream> // U slucaju jezika C++ pozeljno je
2: #include <cstdio> // zaglavlja tipa cstdio umjesto stdio.h i slicno
3: #include <cmath>
4:
5: using namespace std; //Takodjer pozeljna linija u slucaju jezika C++
6:
7: int X[100],Y[100],Obradjen[100];
8: float Mat[100][100];
9:
10: int main(void) {
11:    int N,I,J,K,P;
12:    float Min,Duzina;
13:    ifstream Ulaz("kablovi.in"); 
14:    FILE *Izlaz=fopen("kablovi.out","w");
15:    Ulaz>>N;
16:    for(I=0;I<N;I++) {
17:       Ulaz>>X[I]>>Y[I]; Mat[I][I]=1e30;
18:       for(J=0;J<I;J++)
19:          Mat[I][J]=Mat[J][I]=sqrt(pow(X[I]-X[J],2.0)+pow(Y[I]-Y[J],2.0));
20:    }
21:    Duzina=0; Obradjen[0]=1;
22:    for(K=1;K<N;K++) Obradjen[K]=0;
23:    for(K=1;K<N;K++) {
24:       Min=Mat[0][0];
25:       for(I=0;I<N;I++)
26:          for(J=0;J<N;J++)
27:             if(!Obradjen[I]&&Obradjen[J]&&Mat[I][J]<Min) Min=Mat[P=I][J];
28:       Duzina+=Min; Obradjen[P]=1;
29:    }
30:    fprintf(Izlaz,"%.2f\n",Duzina); 
31:    fclose(Izlaz); 
32:    return 0;
33: }

Moze li mi neko objasnti ovaj zadatak? Imam problema sa datotekama :$ (izmedju ostalog nejasna mi je 14. linija)


[Ovu poruku je menjao Mihajlo Cvetanović dana 02.02.2011. u 10:28 GMT+1]
[ Mihajlo Cvetanović @ 01.02.2011. 23:41 ] @
U toj liniji se otvara fajl s imenom kablovi.out, da bi se u njega nešto upisalo ("w" je od write). Rezultat funkcije je tipa pointer na FILE (što u suštini nije bitno), i tu vrednost koristiš kad želiš da radiš nešto s tim fajlom (u ovom slučaju da upišeš nešto u njega). Detaljnije objašnjenje vidi ovde: http://www.cplusplus.com/reference/clibrary/cstdio/fopen/

Ako još nešto nije jasno postavi konkretno pitanje da bi dobio konkretan odgovor.
[ sannyy @ 02.02.2011. 07:47 ] @
Hvala :)
Samo mi jos nije jasno sta je ovo 1e30 u 17. liniji, je li to neka funkcija iz biblioteke math?
Moze li se na neki drugi nacin rijesiti ovaj zadatak?
[ X Files @ 02.02.2011. 07:58 ] @
^
http://en.wikipedia.org/wiki/Scientific_notation
[ sannyy @ 02.02.2011. 08:18 ] @
Rzumijem... i sumnjala sam na to... ali nisam bas sigurna ni oko cega u C++-u.
A zasto sad taj d2-niz inicijaliziramo tako??
[ sannyy @ 02.02.2011. 08:34 ] @
Izgleda da ja nisam razumjela sustinu ovog zadatka, sta zapravo treba da radi... zato ni kod ne mogu razumjeti :(
[ Mihajlo Cvetanović @ 02.02.2011. 10:02 ] @
Suština algoritma se nalazi u linijama 23-29. Sve pre toga je učitavanje podataka i inicijalizovanje raznih promenljivih. Recimo matrica Mat služi da ubrza algoritam jer se tu čuvaju rastojanja između svake dve tačke, tako da u samom algoritmu ne mora ni jednom da se poziva sqrt, koji bi možda usporio rad.

Šta algoritam radi? Algoritam traži najkraću liniju koja bi povezala onaj skup tačaka koji je algoritam već povezao sa jednom novom tačkom. Algoritmu nije bitno koja će ta nova tačka biti (ali mora biti nova i do tad nepovezana tačka), nego samo da je linija koja je povezala tu novu tačku najkraća od svih dostupnih linija. Algoritmu je tačka 0 polazna. Svaki put kad pronađemo tu minimalnu liniju mi je dodajemo u totalni zbir. Kada se pronađe N-1 takvih linija koje povezuju N tačaka onda smo pronašli naše minimalno drvo koje povezuje sve tačke u grafu.

Za više informacija pođi od sledećeg članka, pa prati razne linkove: http://en.wikipedia.org/wiki/Minimum_spanning_tree