Cod sursa(job #1452525)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 21 iunie 2015 11:49:37
Problema Arbore partial de cost minim Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <cstdio>
#include <vector>
#include <algorithm>

#define cost first
#define x second.first
#define y second.second

using namespace std;

const int Nmax = 200010;
const int Mmax = 400010;

int n , m , i , ans;
int T[Nmax] , rang[Nmax];

pair < int , pair < int , int > > edge[Mmax];

vector < pair < int , int > > ans_edges;

int multime(int node)
{
    if (node != T[node])
        T[node] = multime(T[node]);

    return T[node];
}

void Union(int mult1 , int mult2)
{
    if (rang[mult1] < rang[mult2])
        T[mult1] = mult2;
    else T[mult2] = mult1;

    if (rang[mult1] == rang[mult2])
        rang[mult1]++;
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    scanf("%d %d", &n, &m);
    for (i = 1; i <= m; ++i)
        scanf("%d %d %d", &edge[i].x, &edge[i].y, &edge[i].cost);

    sort(edge + 1 , edge + m + 1);

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

    for (i = 1; i <= m; ++i)
    {
        int m1 = multime(edge[i].x); int m2 = multime(edge[i].y);
        if (m1 != m2)
        {
            Union(m1 , m2);
            ans += edge[i].cost;
            ans_edges.push_back(edge[i].second);
        }
    }

    printf("%d\n%d\n", ans , ans_edges.size());
    for (i = 0; i < ans_edges.size(); ++i)
        printf("%d %d\n", ans_edges[i].first, ans_edges[i].second);

    return 0;
}