Cod sursă (job #625737)

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <ctype.h>

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 != '-');
        n = c - '0';
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		return *this;
	}
};

using namespace std;

const int MAX=10005;
int n,m,k,cnt,a,b,c,cost,mi,r1,r2,ok,t[MAX],rang[MAX],viz[MAX];
struct T{int a,b,c;};
vector < T > mc,v;

bool cmp(T x, T y)
{
    return x.c<y.c;
}

int root(int x)
{
    while(x!=t[x])
        x=t[x];
    return x;
}

void uneste(int x, int y)
{
    if(rang[x]>rang[y])
        t[y]=x;
    if(rang[y]>rang[x])
        t[x]=y;
    if(rang[x]==rang[y])
    {
        t[y]=x;
        rang[x]++;
    }
}

int main()
{
    InParser fin("zapada.in");
    ofstream fout("zapada.out");
    fin >> n >> m >> k;
    for(int i=1;i<=m;i++)
    {
        fin >> a >> b >> c;
        mc.push_back({a,b,c});
    }
    sort(mc.begin(),mc.end(),cmp);
    for(int i=1;i<=n;i++)
        t[i]=i;
    for(int i=0;i<m;i++)
    {
        int rx=root(mc[i].a);
        int ry=root(mc[i].b);
        if(rx!=ry)
        {
            uneste(rx,ry);
            v.push_back(mc[i]);
            cost+=mc[i].c;
        }
    }
    fout << cost << '\n';
    while(k--)
    {
        fin >> a >> b >> c;
        if(v[v.size()-1].c>c)
        {
            v.push_back({a,b,c});
            for(int i=v.size()-1;i>0;i--)
                if(v[i].c<v[i-1].c)
                    swap(v[i],v[i-1]);
                else
                    break;
            mc=v;
            v.clear();
            cost=0;
            for(int i=1;i<=n;i++)
            {
                t[i]=i;
                rang[i]=0;
            }
            for(int i=0;i<n;i++)
            {
                int rx=root(mc[i].a);
                int ry=root(mc[i].b);
                if(rx!=ry)
                {
                    uneste(rx,ry);
                    v.push_back(mc[i]);
                    cost+=mc[i].c;
                }
            }
            fout << cost << '\n';
        }
        else
            fout << cost << '\n';
    }
	return 0;
}