Cod sursă (job #749768)

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


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

struct nodi{
    int x,y,dis;
};

vector<int> vf;
///int vf[13];
vector<nodi> v;
vector<nodi> nece;

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

int n;

int tot;
int maxim;

int caut1;
int inline caut(int st,int dr)
{
    if(st>=dr)
        return st;
    int mij=(st+dr)>>1;
    if(v[mij].dis==caut1)
        return mij;
    if(v[mij].dis>caut1)
        return caut(st,mij);
    else
        return caut(mij+1,dr);
}
int N;
void inline kruskal()
{
    tot=0;
    maxim=0;
    int scos=0;
    vector<nodi>::iterator el;
    for(el=v.begin();el!=v.end() && scos<N;++el)
    {
        if(ga(vf[el->y])!=ga(vf[el->x]))
        {
            nodi a=*el;
            vf[ga(el->x)]=vf[el->y];
            maxim=max(maxim,el->dis);
            tot+=(el->dis);
            nece.push_back(*el);
            scos++;
        }
    }
}

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