Cod sursă (job #676096)

#include <bits/stdc++.h>







using namespace std;







ifstream fin("zapada.in");



ofstream fout("zapada.out");







struct vrajeala



{



    int x, y, c;



    bool operator < (const vrajeala A) const



    {



        return c < A.c;



    }



}a[200005];



vector <vrajeala> ales;



struct DSU



{



    vector <int> t;



    DSU(int n)



    {



        t.resize(n + 5);



    }







    void Union(int x, int y)



    {



        t[x] = y;



    }







    int Find(int x)



    {



        int r = x, y;



        while (t[r])



            r = t[r];







        while (x != r)



        {



            y = t[x];



            t[x] = r;



            x = y;



        }







        return r;



    }



};



int n, m, q;



void Test_Case()



{



    int i, nrcc, x, y, apm = 0, c;



    fin >> n >> m >> q;



    nrcc = n;



    DSU tree(n);



    for (i = 1; i <= m; i++)



        fin >> a[i].x >> a[i].y >> a[i].c;



    sort(a + 1, a + m + 1);



    for (i = 1; i <= m and nrcc > 1; i++)



    {



        x = tree.Find(a[i].x);



        y = tree.Find(a[i].y);



        if (x != y)



        {



            tree.Union(x, y);



            ales.push_back(a[i]);



            nrcc--;



            apm += a[i].c;



        }



    }



    fout << apm << "\n";



    while (q--)



    {



        fin >> x >> y >> c;



        if (c > ales.back().c)



        {



            fout << apm << "\n";



            continue;



        }



        ales.push_back({ x, y, c });



        for (i = ales.size() - 1; i >= 1 and ales[i].c < ales[i - 1].c; i--)



            swap(ales[i], ales[i - 1]);



        DSU tree(n);



        apm = 0;



        nrcc = n;



        for (i = 0; i < ales.size() and nrcc > 1; i++)



        {



            x = tree.Find(ales[i].x);



            y = tree.Find(ales[i].y);



            if (x != y)



            {



                tree.Union(x, y);



                nrcc--;



                apm += ales[i].c;



            }



        }



        fout << apm << "\n";







    }



}







int main()



{



    int t;





    t = 1;



    while (t--)



        Test_Case();







    return 0;



}