Cod sursă (job #626025)

#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];

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;
}

void Krsk_1()
{
    int f = 1;

    while(k < n - 1)
    {
        if(P[ Regat_1[f].x ] != P[ Regat_1[f].y ])
        {
            k++;
            sm += Regat_1[f].c;

            Regat_2[k] = Regat_1[f];

            idx_1 = P[ Regat_1[f].x ];
            idx_2 = P[ Regat_1[f].y ];

            for(int j = 1; j<= n; j++)
                if(P[j] == idx_2) P[j] = idx_1;

        }

        f++;
    }
}

void Krsk_2()
{
    int f = 1;

    while(m < n - 1)
    {
        if(P[ Regat_2[f].x ] != P[ Regat_2[f].y ])
        {
            m++;
            sm += Regat_2[f].c;

            Regat_1[m] = Regat_2[f];

            idx_1 = P[ Regat_2[f].x ];
            idx_2 = P[ Regat_2[f].y ];

            for(int j = 1; j<= n; j++)
                if(P[j] == idx_2) P[j] = idx_1;

        }

        f++;
    }
}

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

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;
            P[i]=i;
        }

    sort(Regat_1 ,Regat_1 + m + 1,St);

    Krsk_1();

    int ok=1;// 1 - Regatul_2 este construit , 0 - Regatul_1 este construit

    fout << sm << "\n";


    for(int i = 1;i <= q; i++)
    {
        if(ok == 1)
        {
            k++;

            m=0;
            sm=0;
            ok=0;

            fin >> Regat_2[k].x >> Regat_2[k].y >> Regat_2[k].c;

            for( int j = k ; j > 1; j-- )
            {
                if( Regat_2[j].c > Regat_2[j-1].c)
                break;
                    
                swap(Regat_2[j], Regat_2[j-1]);
            }

            Ump();

            Krsk_2();
        }
        else
        {
            m++;

            k=0;
            sm=0;
            ok=1;

            fin >> Regat_1[m].x >> Regat_1[m].y >> Regat_1[m].c;

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

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

            Ump();

            Krsk_1();
        }

       fout <<  sm << "\n";

    }

    return 0;


}