Cod sursă (job #626046)

#include <iostream>
#include <algorithm>
#include <fstream>

using namespace std;

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

struct Street{
    int x,y,c;
} Regat_1[100005], Regat_2[100005];

int n,m,k,q,sm;

int P[10005],T[10005];

int idx_1, idx_2;

void Tp()
{
    for(int i = 1; i <= k ; i++)
        cout << Regat_2[i].x <<" " << Regat_2[i].y << " " <<  Regat_2[i].c << "\n";
}

bool St(Street a ,Street b)
{
    return a.c < b.c;
}

int Root(int a)
{
    if(T[a] != a)
        T[a]=Root(T[a]);

    return T[a];
}

void Unt(int a,int b)
{
    if(P[a] < P[b])
        {
            T[a] = b;
            P[b] += P[a];
        }
        else
        {
            T[b]= a;
            P[a] += P[b];
        }
    
}

void Clean()
{
    for( int i = 1;i <= n; i++)
    {
        P[i] = 1;
        T[i] = i;
    }
}

void Krsk()
{ 
    k = 0;
    sm = 0;
    Clean();

    for(int f = 1;k < n - 1; f++)
    {
            idx_1 = Root( Regat_1[f].x );
            idx_2 = Root( Regat_1[f].y );

        if(idx_1 != idx_2 )
        {
            k++;
            sm += Regat_1[f].c;

            Regat_2[k] = Regat_1[f];

            Unt(idx_1, idx_2);
        }
    }

    for(int i = 1;i < n; i++)
    {
        Regat_1[i] = Regat_2[i];
    }

    fout << sm << "\n";
}

int main()
{
    fin >> n >> m >> q;

    for(int i = 1; i <= m ; i++)
            fin >> Regat_1[i].x >> Regat_1[i].y >> Regat_1[i].c;
        
    sort(Regat_1 ,Regat_1 + m + 1,St);

    Krsk();


    for(int i = 1;i <= q; i++)
    {
       fin >> Regat_1[n].x >> Regat_1[n].y >> Regat_1[n].c;

       for(int j = n; j > 1; j--)
       {
           if(Regat_1[j].c >= Regat_1[j-1].c)break;

           swap(Regat_1[j],Regat_1[j-1]);
       }

       Krsk();
    }
    return 0;
}