Cod sursă (job #749535)

#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 co=0;
int n,maxi;
vector<nodi> v;
vector<nodi> nece;
vector<int> vf;
int tot;
int N;

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

int ga(int nod)
{
    int val;
    val=vf[nod]-co;
    if(val<=0)
    {
        vf[nod]=nod+co;
        return nod+co;
    }
    if(val==nod)
        return vf[nod];
    vf[nod]=ga(val);
    return vf[nod];
}

void kruskal()
{
    vector<nodi>::iterator el;
    int alese=0;
    for(el=v.begin();el!=v.end() && alese<N;el++)
    {
        if(ga(el->fi)!=ga(el->pr))
        {
            alese++;
            tot=tot+(el->dis);
            vf[vf[el->fi]-co]=vf[el->pr];
            maxi=max(el->dis,maxi);
            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;
         });
    N=n-1;
    kruskal();
    v.clear();
    v=nece;
    fout<<tot<<'\n';
    vector<nodi>::iterator poz;
    poz=v.begin();
    for(int k=1;k<=K;k++)
    {
        fin>>nod.pr>>nod.fi>>nod.dis;
        if(maxi<nod.dis)
        {
            fout<<tot<<'\n';
            continue;
        }
        caut1=nod.dis;
        v.insert(v.begin()+caut(0,N),nod);
        ///n++;
        ///vf.push_back(0);
      ///  for(int c=1;c<=n;c++)
           /// vf[c]=c;
        co=co+11000;
        tot=0;
        nece.clear();
        kruskal();
        v=nece;
        fout<<tot<<'\n';
    }
    return 0;
}