Cod sursă (job #522446)

#include <bits/stdc++.h>

using namespace std;
ifstream in("zapada.in");
ofstream out("zapada.out");
int n,m,k,z,nr,ans,cmin,mx,sz;
int a,b,p[10005];
struct zapada
{
    int x,y;
    int c;
    bool operator<(const zapada &aux) const
    {
        return c<aux.c;
    }
}v[100005],pom[100005];
int find(int x)
{
    int r=x;
    while(p[r]!=r) r=p[r];
    while(p[x]!=r)
    {
        int aux=p[x];
        p[x]=r;
        x=p[x];
    }
    return r;
}
void Union(int x,int y)
{
    int rx=find(x);
    int ry=find(y);
    if(rx!=ry) p[rx]=ry;
}
void kruskal(zapada copac[],zapada v[],int m)
{
    int cr=0;
    cmin=0;
    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=m;i>1;i--)
        if(copac[i].c<copac[i-1].c) swap(copac[i],copac[i-1]);
        else break;
    sz=0;
    for(int i=1;i<=m;i++)
    {
        if(find(copac[i].x)!=find(copac[i].y))
        {
            Union(copac[i].x,copac[i].y);
            cmin+=copac[i].c;
            v[++sz]=copac[i];
            mx=copac[i].c;
            cr++;
        }
        if(cr==sz-1) break;
    }
}
int main()
{
    in>>n>>m>>k;
    for(int i=1;i<=m;i++)
        in>>v[i].x>>v[i].y>>v[i].c;
    sort(v+1,v+m+1);
    kruskal(v,pom,m);
    out<<cmin<<'\n';
    for(int i=1;i<=k;i++)
    {
        in>>a>>b>>z;
        if(z>=mx)
        {
            out<<cmin<<'\n';
            continue;
        }
        else
        {
            sz++;
            pom[sz]={a,b,z};
            kruskal(pom,pom,sz);
            out<<cmin<<'\n';
        }
    }
    return 0;
}