/* Algoritmul lui Prim (determină un APM într-un graf ponderat conex) */ /* V.5 */

#include <iostream> // cu extensia .h pentru Borland C++ 3.1
#include <fstream>
using namespace std; // a elimina/comenta, în cazul Borland C++ 3.1

ifstream fs("muchii.txt"); // are structura: [ nr. vârfuri ] [ nr. muchii ] [ vf1, vf2, cost ]*
int nr_vf, nr_eg;   // identificatorii "lungi" (în loc de n, m) evită confuzii la copiere!

typedef struct { int beg, end; /* capetele muchiei */ double cost; } muchie;

muchie * M;  // tabloul muchiilor grafului
int * APM;  // rangurile celor (n-1) muchii din M[] alese în APM

int *za; // vizează un tablou auxiliar de "recrutat / nerecrutat" (folosit de mai multe funcţii)

void init(); // internalizează datele din fişier; alocă M[], APM[], za[]
int cut_min(); // care muchie are cost minim, între cele care leagă "taberele" la un moment dat
void apm_Prim(int); // completează APM[], folosind za[] şi cut_min()

int main() { double cost_apm = 0; int i;
    init();
    cout << "vârful de plecare: "; cin >> i;

    apm_Prim(i - 1); // APM[] va conţine rangurile muchiilor selectate în A.P.M.

    for (i = 0; i < nr_vf - 1; i++) { // afişare APM şi cost
        int rm = APM[i];
        cout << (M[rm].beg + 1) << " - " << (M[rm].end + 1) << '\t' << M[rm].cost << '\n';
        cost_apm += M[rm].cost;
    }
    cout << "\nCostul minim = " << cost_apm << '\n';

    delete [] APM; // eliberarea zonelor alocate pentru execuţia curentă
    delete [] M; delete [] za;
    return 0;
}

void init() {  int i;
    fs >> nr_vf >> nr_eg;
    APM = new int[nr_vf - 1];
    M = new muchie [nr_eg]; // main() va trebui să elibereze zonele alocate aici
    for (i = 0; i < nr_eg; i++) {
        fs >> M[i].beg >> M[i].end >> M[i].cost;
        M[i].beg--; M[i].end--; // în fişier vârfurile 1..n dar în tablou 0..(n-1)
    }
    za = new int[nr_vf];
    for (i = 0; i < nr_vf; i++) // iniţializează toate vârfurile ca "nerecrutate" în APM
        za[i] = 0;
}

int cut_min() { // za[i] = 1 sau 0, după cum vârful i a fost sau nu "recrutat"
    int rm; double q = 1.E15; // q > costurile existente
    for (int i = 0; i < nr_eg; i++)
        if(za[M[i].beg] ^ za[M[i].end]) // capetele muchiei trebuie să fie din "tabere" diferite
            if(M[i].cost < q) {
                rm = i;
                q = M[i].cost;
            }
    return rm; // rangul celei mai "scurte" muchii care uneşte un vârf vizitat cu unul nevizitat
}

void apm_Prim(int start) { // vârful de start (oarecare, când costurile sunt distincte: APM unic)
    za[start] = 1; // marchează capătul primei muchii care se va include în APM
    for (int i = 0; i < nr_vf - 1; i++) {
        int rm = cut_min();
        APM[i] = rm; // muchia de rang rm este inclusă în APM (a i-a muchie a arborelui)
        if(za[M[rm].beg])
            za[M[rm].end] = 1; // marchează şi celălalt capăt al muchiei incluse în APM
        else za[M[rm].beg] = 1;
    }
}