Cod sursă (job #676080)

#include <bits/stdc++.h>

#define N 100005

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;

    }

};
struct muchie2

{

    int nod,cost;

    bool operator < (const muchie2 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;
multiset<muchie2>a[N];
void Kruskal()

{

    sort(edges.begin(),edges.end());

    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);
	        a[i.x].insert({i.y,i.cost});
	        a[i.y].insert({i.x,i.cost});
            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});

    Kruskal();

    fout<<S<<"\n";
    //for(auto x:sol) cout<<x.x<<" "<<x.y<<"\n";
	//for(i=1;i<=n;i++)
    //{
    //    for(auto x:a[i]) cout<<x.nod<<" ";
    //    cout<<"\n";
    //}
    for(i=1;i<=k;i++)

    {

        fin>>x>>y>>c;for(int j=1;j<=n;j++) t[j]=0;

        edges.push_back({x,y,c});
        a[x].insert({y,c});a[y].insert({x,c});
        int m=0,nod1,nod2;
        for(auto i:a[x])
            if(a[x].size()>1&&i.cost>m)m=i.cost,nod1=x,nod2=i.nod;
        for(auto i:a[y])
            if(a[y].size()>1&&i.cost>m) m=i.cost,nod1=y,nod2=i.nod;
        a[x].erase({y,c});a[y].erase({x,c});
        S-=m;S+=c;
        fout<<S<<"\n";

    }

    return 0;

}