og_network.cpp

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++;
    }
}