/* 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
#include<vector>
ifstream fs("muchii.txt"); // are structura: [ nr. varfuri ] [ nr. muchii ] [ vf1, vf2, cost ]*
int nr_vf, nr_eg;   // identificatorii "lungi" (in loc de n, m) evita confuzii la copiere!

typedef struct
{
    int beg,end; /* capetele muchiei */
    double cost;
} muchie;
vector <muchie> M;
  // tabloul muchiilor grafului
vector <int> za;
vector <int> APM;

void init()
{
    int i;
    fs>> nr_vf >> nr_eg;

     // main() va trebui sa 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--; // in fisier varfurile 1..n dar în tablou 0..(n-1)
    }

    for (i = 0; i < nr_vf; i++) // initializeaza toate varfurile ca "nerecrutate" in APM
        za[i] = 0;
}

int cut_min()   // za[i] = 1 sau 0, dupa cum varful 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 sa fie din "tabere" diferite
            if(M[i].cost < q)
            {
                rm = i;
                q = M[i].cost;
            }
    return rm; // rangul celei mai "scurte" muchii care uneste un varf vizitat cu unul nevizitat
}

void apm_Prim(int start)   // varful de start (oarecare, când costurile sunt distincte: APM unic)
{
    za[start] = 1; // marcheaza capatul 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 inclusa in APM (a i-a muchie a arborelui)
        if(za[M[rm].beg])
            za[M[rm].end] = 1; // marcheaza şi celalalt capat al muchiei incluse in APM
        else za[M[rm].beg] = 1;
    }
}
int main()
{
    double cost_apm = 0;
    int i;
    init();
    cout << "vârful de plecare: ";
    cin >> i;

    apm_Prim(i - 1); // APM[] va contine rangurile muchiilor selectate in A.P.M.

    for (i = 0; i < nr_vf - 1; i++)   // afisare APM si 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';
    return 0;
}