Cod sursă (job #749536)

#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;

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

struct nodi{
    int pr,fi,dis;
};

int n;
vector<nodi> v;
vector<int> vf;
vector<nodi> nece;
int tot;

int ga(int nod)
{
    if(vf[nod]==nod)
        return nod;
    vf[nod]=ga(vf[nod]);
    return vf[nod];
}

void kruskal()
{
    vector<nodi>::iterator el;
    int alese=0;
    for(el=v.begin();el!=v.end() && alese<n-1;el++)
    {
        if(ga(el->fi)!=ga(el->pr))
        {
            alese++;
            tot=tot+(el->dis);
            vf[vf[el->fi]]=vf[el->pr];
            nece.push_back(*el);
            ///ga(vf[el->fi]);
        }
    }
}

int caut1;

int caut(int st,int dr)
{
    if(st>=dr)
        return st;
    int mij=(st+dr)>>1;
    if(v[mij].dis>caut1)
        return caut(st,mij-1);
    return caut(mij+1,dr);
}


int main()
{
    int m,K;
    fin>>n>>m>>K;
    nodi nod;
    for(int k=1;k<=m;k++)
    {
        fin>>nod.pr>>nod.fi>>nod.dis;
        v.push_back(nod);
    }
    vf.resize(n+1);
    for(int k=1;k<=n;k++)
        vf[k]=k;
    sort(v.begin(),v.end(),[](nodi a,nodi b){
            return a.dis<b.dis;
         });
    kruskal();
    fout<<tot<<'\n';
    vector<nodi>::iterator poz;
    poz=v.begin();
    int mini=tot;
    v=nece;
    int N=n-1;
    for(int k=1;k<=K;k++)
    {
        fin>>nod.pr>>nod.fi>>nod.dis;
        if(mini<nod.dis)
            fout<<mini<<'\n';
        else
        {
            caut1=nod.dis;
            v.insert(v.begin()+caut(0,N),nod);
            for(int c=1;c<=n;c++)
                vf[c]=c;
            tot=0;
            nece.clear();
            kruskal();
            v=nece;
            fout<<mini<<'\n';
            mini=tot;
        }
    }
    return 0;
}