Cod sursă (job #676593)

#include<fstream>
#include<algorithm>
#include<vector>
#include<cstring>
#define N 10005
using namespace std;
ifstream fin ("zapada.in");
ofstream fout ("zapada.out");
int n,m,k,a,b,c;
int cost;
int t[N],viz[N],rang[N];
struct T{int a,b,c;};

vector<T>mc,v;
bool comp(T x, T y){return x.c<y.c;}
int Rad(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;
    else{
        t[x]=y;
        if(rang[x]==rang[y])
            rang[y]++;
    }
}
int main()
{
  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(),comp);
  for(int i=1;i<=n;i++)t[i]=i;
  for(int i=0;i<m;i++)
  {
      int rx=Rad(mc[i].a);
      int ry=Rad(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=Rad(mc[i].a);
            int ry=Rad(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;
}