Cod sursă (job #521981)

#include <bits/stdc++.h>

using namespace std;
ifstream fin("zapada.in");
ofstream fout("zapada.out");

int i, j, cost, ct, n, m, k, Max, rr[10005], p[10005];

struct elem
{
    int x, y, c;
} st[100005];

int Find(int x)
{
    int r=x;
    while(p[r]!=r)
        r=p[r];
    while(p[x]!=r)
    {
        int tmp=p[x];
        p[x]=r;
        x=tmp;
    }
    return r;
}

void Union(int x, int y)
{
    if(rr[x]>rr[y])
        p[y]=x, rr[x]++;
    else
        p[x]=y, rr[y]++;
}

int cmp(elem a, elem b)
{
    return a.c<b.c;
}

void apm()
{
    sort(st+1, st+m+1, cmp);
    for(int i=1; i<=n; i++)
    {
        p[i]=i;
        rr[i]=1;
    }
    Union(st[1].x, st[1].y);
    cost=st[1].c;
    ct=2;
    Max=cost;
    while(1)
    {
        int j=2;
        while(j<=m && Find(st[j].x)==Find(st[j].y))
            j++;
        Union(Find(st[j].x), Find(st[j].y));
        if(j==m+1)
            break;
        cost+=st[j].c;
        Max=max(Max, cost);
    }
    fout << cost << "\n";
}

int main()
{
    fin >> n >> m >> k;
    for(int i=1; i<=m; i++)
        fin >> st[i].x >> st[i].y >> st[i].c;
    apm();
    while(k--)
    {
        int a, b, c;
        fin >> a >> b >> c;
        if(c > Max)
            fout << cost << "\n";
        else
        {
            st[++m].x=a;
            st[m].y=b;
            st[m].c=c;
            apm();
        }
    }
    return 0;
}