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