Cod sursă (job #292133)

#include<stdio.h>
#include<algorithm>
using namespace std;
const int INF = 100005;
const int M = 100005, N = 10005;
struct muchii
{
    int x, y, cost;
};
muchii v[M], clean[N];
int rad[N];
bool cmp (muchii a, muchii b)
{
    if (a.cost < b.cost)
        return true;
    return false;
}
int radacina (int x)
{
    int r = rad[x];
    while (r != rad[r])
        r = rad[r];
    int aux;
    while (x != rad[x])
    {
        aux = rad[x];
        rad[x] = r;
        x = aux;
    }
    return r;
}
void uneste (int x, int y)
{
    int radX = radacina (x), radY = radacina (y);
        rad[radX] = radY;
}
void init (int n)
{
    for (int i = 1; i <= n; i++)
        rad[i] = i;
}
int main ()
{
    FILE *in, *out;
    in = fopen ("zapada.in", "r");
    out = fopen ("zapada.out", "w");
    int n, m, k;
    fscanf (in, "%d %d %d", &n, &m, &k);
    int i;
    for (i = 1; i <= m; i++)
        fscanf (in, "%d%d%d", &v[i].x, &v[i].y, &v[i].cost);
    sort (v + 1, v + m + 1, cmp);
    init(n);
    int j, s = 0, ct = 0;
    for (j = 1; j <= m; j++)
    {
        if (radacina(v[j].x) != radacina(v[j].y))
        {
            s += v[j].cost;
            clean[++ct] = v[j];
            uneste (v[j].x, v[j].y);
        }
    }
    fprintf (out, "%d\n", s);
    for (i = 1; i <= k; i++)
    {
        s = 0;
        init (n);
        ++ct;
        fscanf (in, "%d%d%d", &clean[ct].x, &clean[ct].y, &clean[ct].cost);
        sort (clean + 1, clean + ct + 1, cmp);
        for (j = 1; j <= ct; j++)
            if (radacina(clean[j].x) != radacina(clean[j].y))
            {
                s += clean[j].cost;
                uneste (clean[j].x, clean[j].y);
            }
        fprintf (out, "%d\n", s);
    }
    return 0;
}