Cod sursa(job #1547781)

Utilizator BaweeLazar Vlad Bawee Data 9 decembrie 2015 21:35:28
Problema Arbore partial de cost minim Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

const int maxn = 400001;
int n,m,x[maxn],y[maxn],c[maxn],ind[maxn],grup[maxn],indice[maxn];
int sum;
vector <int> sol;

bool cmp(const int& x,const int& y)
{
    return c[x] < c[y];
}

int grupa(int x)
{
    if(grup[x] == x) return x;
    grup[x] = grupa(grup[x]);
    return grup[x];
}

void reuniune(int x, int y)
{
    grup[grupa(x)] = grupa(y);
}

int main()
{
    f >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        f >> x[i] >> y[i] >> c[i];
        indice[i] = i;
    }

    for(int i = 1; i <= n; ++i) grup[i] = i;

    sort(indice + 1, indice + m + 1, cmp);

    for(int i = 1; i <= m; i++)
        if(grupa(x[indice[i]]) != grupa(y[indice[i]]))
        {
            sum += c[indice[i]];
            reuniune(x[indice[i]],y[indice[i]]);
            sol.push_back(indice[i]);
        }

    g << sum << "\n" << n - 1 << "\n";
    for(vector<int>::iterator it = sol.begin(); it != sol.end(); ++it)
        g << x[*it] << " " << y[*it] << "\n";
    return 0;
}