Cod sursa(job #2012768)

Utilizator workwork work work Data 19 august 2017 16:09:45
Problema Arbore partial de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>

#define f first
#define s second

using namespace std;

FILE *F=fopen("apm.in", "r"), *G=fopen("apm.out", "w");

int n, m, x, y, c, t[200004], r[200004], k, tx, ty, S;
pair<int, int> sol[400004];
pair<int, pair<int, int> > p[400004];

int Find(int x)
{
    int R, y;

    for(R = x; R != t[R]; R = t[R]);

    for(; x != t[x];)
    {
        y = t[x];
        t[x] = R;
        x = y;
    }
    return R;
}

void Unite(int x, int y)
{
    if(r[x] >= r[y]) t[y] = x;
    else t[x] = y;

    if(r[x] == r[y]) r[x] ++;
}

int main()
{
    fscanf(F, "%d %d ", &n, &m);
    for(int i = 1; i <= m; ++ i)
    {
        fscanf(F, "%d %d %d ", &x, &y, &c);
        p[i] = {c, {x, y}};
    }
    sort(p + 1, p + m +1);
    for(int i = 1; i <= n; ++ i) t[i] = i, r[i] = 1;
    for(int i = 1; i <= m; ++ i)
    {
         x = p[i].s.f;
         y = p[i].s.s;
         tx = Find(x);
         ty = Find(y);
         if(tx != ty)
             sol[++ k] = {x, y}, Unite(tx, ty), S += p[i].f;
    }
    fprintf(G, "%d\n", S);
    for(int i = 1; i <= k; ++ i)
        fprintf(G, "%d %d\n", sol[i].f, sol[i].s);
    return 0;
}