ve_feszitofa.pas

Letöltés: ve_feszitofa.cpp

#include <iostream>
#include <stdio.h>

struct el {
    unsigned int kPont, vPont, suly;
    el(unsigned int k, unsigned int v, unsigned int s) {
        kPont = k;
        vPont = v;
        suly = s;
    }
};

el *elek[800];
unsigned int apak[40], pontdb, eldb = 0;
long megtak;

using namespace std;

void beolvas() {
    unsigned int i, j;
    unsigned int tar;
    FILE *file = fopen("network.txt", "r");
    fscanf(file, "%i", &pontdb);
    megtak = 0;
    for (i = 0; i < pontdb; i++) {
        apak[i] = i;
        for (j = 0; j < pontdb; j++) {
            if (j+1 == pontdb) fscanf(file, "%i", &tar);
            else fscanf(file, "%i ", &tar);
            if (j >= i && tar != 0) {
                elek[eldb] = new el(i, j, tar);
                megtak += elek[eldb]->suly;
                eldb++;
            }
        }
    }
}

void elekrendez() {
    unsigned int i, j;
    el *tempEl;
    for (i = 0; i < eldb-1; i++) {
        for (j = i+1; j < eldb; j++) {
            if (elek[j]->suly < elek[i]->suly) {
                tempEl = elek[j];
                elek[j] = elek[i];
                elek[i] = tempEl;
            }
        }
    }
}

unsigned int apa(unsigned int pont) {
    unsigned int retValue;
    if (apak[pont] == pont) retValue = pont;
    else retValue = apa(apak[pont]);
    apak[pont] = retValue;
    return retValue;
}

int main(int argc, char **argv) {
    unsigned int i;
    beolvas();
    elekrendez();
    for (i = 0; i < eldb; i++) {
        if (apa(elek[i]->kPont) != apa(elek[i]->vPont)) {
            apak[apa(elek[i]->kPont)] = elek[i]->vPont;
            megtak -= elek[i]->suly;
        }
    }
    printf("%li\n", megtak);
    return 0;
}