Cod sursă (job #625860)

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

class InParser {
private:
    FILE *fin;
    char *buff;
    int sp;
 
    char read_ch() {
        ++sp;
        if (sp == 4096) {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }
 
public:
    InParser(const char* nume) {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }
    
    InParser& operator >> (int &n) {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
    
    InParser& operator >> (long long &n) {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-');
        long long sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
};
 
InParser fin("zapada.in");
ofstream fout("zapada.out");
int t[10010],rang[10010];
int n, m, K, lung;
struct muchie{
    int x,y,c;
};
muchie v[110000];
bool cmp(muchie a, muchie b)
{
    return a.c < b.c;
}
int radacina(int x)
{
    if(t[x]==0)
        return x;
    int k = radacina(t[x]);
    t[x]=k;
    return k;
}
void uneste(int x,int y)
{
    int rx=radacina(x),ry=radacina(y);
    if(rang[rx] > rang[ry])
        t[ry]=rx;
    else if(rang[rx] < rang[ry])
        t[rx]=ry;
    else
    {
        rang[rx]++;
        t[ry]=rx;
    }
}
int Kruskal(int n)
{
    int poz=0;
    for(int i=1;i<=n;i++)
        t[i]=rang[i]=0;
    int cost=0,nr=0;
    for(int i=1;i<=lung;i++)
    {
        muchie it=v[i];
        if(radacina(it.x) != radacina(it.y))
        {
            v[++poz]=it;
            cost += it.c;
            uneste(it.x,it.y);
            nr++;
            if(nr == n-1)
                break;
        }
    }
    lung=n-1;
    return cost;
}
void addsort(muchie x,int &n)
{
    int i=n;
    while(x.c < v[i].c && i>=1)
    {
        v[i+1]=v[i];
        i--;
    }
    v[i+1]=x;
    n++;
}
int main() {
    fin>>n>>m>>K;
    for(int i=1;i<=m;i++)
    {
        muchie x;
        fin>>x.x>>x.y>>x.c;
        v[++lung]=x;
    }
    sort(v+1,v+lung+1,cmp);
    int COST = Kruskal(n);
    fout<<COST<<'\n';
    for(int i=1;i<=K;i++)
    {
        muchie ct;
        fin>>ct.x>>ct.y>>ct.c;
        if(ct.c > v[lung].c)
        {
            fout<<COST<<'\n';
            continue;
        }
        addsort(ct,lung);
        COST=Kruskal(n);
        fout<<COST<<'\n';
    }
    return 0;
}