Letöltés: og_network.cpp #include <cstdio> #include <iostream> #include <algorithm> #include <math.h> using namespace std; struct elek { int suly; int a; int b; }; void beolvas(char*); void atir(); bool compare(elek, elek); int holvan(int); void kruskal(); int n,temp; char c; int** a; int* apa; elek* el; int elsz; int* kimenet; int kisz; int kisuly; int sum; int main() { beolvas("network.txt"); atir(); kruskal(); //cout << "\n"; /* for(int i=0; i<kisz; i++) { cout << kimenet[i] <<" "; }*/ // cout <<"\nKisuly "<< kisuly; // cout <<"\nSum \n"<< sum; cout << sum-kisuly; } void beolvas(char* file) { FILE* be = fopen(file, "r"); n=40; a = new int*[n]; for(int i=0; i<n; i++) { a[i] = new int[n]; for(int j=0; j<n; j++) { fscanf(be, "%d", &a[i][j]); if(a[i][j]!=0) { elsz++; } } } elsz=elsz/2; fclose(be); } void atir() { el=new elek[elsz+1]; int elsz2=0; apa=new int[n]; sum=0; for(int i=0; i<n; i++) { apa[i]=i; for(int j=i; j<n; j++) { if((a[i][j]!=0) && (i!=j)) { el[elsz2].a=i; el[elsz2].b=j; el[elsz2].suly=a[i][j]; sum+=el[elsz2].suly; elsz2++; } } } sort(el,el+elsz,compare); /*for(int i=0; i<elsz; i++) { printf("%d %d %d \n", el[i].suly, el[i].a,el[i].b); }*/ // cout << "\n"; } bool compare(elek x, elek y) { return(x.suly<y.suly); } int holvan(int x) { if(x==apa[x]) { return x; } else { /////////////////////////////optimalizálás int rek_apa; rek_apa = holvan(apa[x]); apa[x]=rek_apa; return rek_apa; /////////////////////////////// // return holvan(apa[x]); } } void kruskal() { int db=0; int i=0; kimenet=new int[elsz]; kisuly=0; kisz=0; while((db<n-1) && (i<elsz)) { int x=el[i].a; int y=el[i].b; int hx=holvan(x); int hy=holvan(y); // cout << i << " x: " << x <<" h(x): " <<holvan(x)<<" y: "<<y<< " h(y): " << holvan(y)<< "\n"; if(hx!=hy) { kimenet[kisz]=i; kisz++; kisuly+=el[i].suly; apa[hx]=hy; db++; } i++; } } |