Cod sursă (job #676094)

#include <bits/stdc++.h>

#define N 200005

using namespace std;

ifstream fin("zapada.in");

ofstream fout("zapada.out");

struct muchie

{

    int x,y,cost;

    bool operator < (const muchie x) const

    {

        return x.cost>cost;

    }

};

int n,m,k,t[N],nrcc,S;

void Union(int x,int y)

{

    t[y]=x;

}

int Find(int x)

{

    int rad=x,y;

    while(t[rad]) rad=t[rad];

    while (x != rad)

    {

        y = t[x];

        t[x] = rad;

        x = y;

    }

    return rad;

}

vector<muchie>edges,sol;

void Kruskal1()

{


    nrcc=n;S=0;

    for(auto i:edges)

        if(nrcc>1)

    {

        int x=Find(i.x);

        int y=Find(i.y);

        if(x!=y)

        {

            Union(x,y);

            nrcc--;
	        sol.push_back(i);
            S+=i.cost;

        }

    }

}
void Kruskal2()

{


    nrcc=n;S=0;

    for(auto i:sol)

        if(nrcc>1)

    {

        int x=Find(i.x);

        int y=Find(i.y);

        if(x!=y)

        {

            Union(x,y);

            nrcc--;
            S+=i.cost;

        }

    }

}
int main()

{

    int i,x,y,c,k;

    fin>>n>>m>>k;

    while(m--)

        fin>>x>>y>>c,

        edges.push_back({x,y,c});
	sort(edges.begin(),edges.end());
    Kruskal1();

    fout<<S<<"\n";

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

    {

        fin>>x>>y>>c;
        if(c>sol.back().cost) {fout<<S<<"\n";continue;}
        memset(t,0,sizeof(t));sol.push_back({x,y,c});
        for(int j=sol.size()-1;j>0&&sol[j].cost<sol[j-1].cost;j--)
            swap(sol[j],sol[j-1]);

        Kruskal2();fout<<S<<"\n";

    }

    return 0;

}