Cod sursă (job #324743)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct punct
{
    int x, y, c, d;
}u[100002];

int n, m, i, j, f, Min=999999999;

int cmp(punct x, punct y)
{
    return (x.c<y.c);
}
int root(int x, int t[])
{
    while(t[x]!=x) x=t[x];
    return x;
}
void unific (int x, int y, int p[], int t[])
{
    if (p[x]<p[y]) t[x]=y;
    if (p[x]>p[y]) t[y]=x;
    if (p[x]==p[y]){
        t[y]=x;
        p[x]++;
    }
}
void cauta(int m)
{
    int t[100002], p[100002],i, k=0, rx, ry, ct=0;
    memset(p, 0, sizeof(p));
    for (i=1; i<=m; i++) t[i]=i;
    sort(u+1, u+m+1, cmp);
    i=1;
    while (k<n-1){
        rx=root(u[i].x, t);
        ry=root(u[i].y, t);
        if (rx!=ry){
            k++;
            ct+=u[i].c;
            unific(rx, ry, p, t);
        }
        i++;
    }
    printf("%d\n", ct);
    if (ct<Min) Min=ct;
}
int main()
{
    freopen("zapada.in","r",stdin);
    freopen("zapada.out","w",stdout);

    scanf("%d%d%d", &n, &m, &f);
    for (i=1; i<=m; i++){
        scanf("%d%d%d", &u[i].x, &u[i].y, &u[i].c);
    }

    cauta(m);
    for (i=1; i<=f; i++){
        scanf("%d%d%d", &u[m+i].x, &u[m+i].y, &u[m+i].c);
        if (u[m+i].c>Min) printf("%d\n", Min);
        else cauta(m+i);
    }
    return 0;
}