Cod sursă (job #662774)

#include <bits/stdc++.h>
 
using namespace std;
 
ifstream fin("zapada.in");
ofstream fout("zapada.out");
 
const int nmax=1e4+7;
int n,m,k;
int x,y,c;
vector<pair<short,pair<short,short> > > muchii;
vector<pair<short,short> > vecini[nmax];
short tata[nmax];
int h[nmax];
int cost_total;
int dd[nmax];
bool gasit;
bool vizitat[nmax];
 
int tabs(int nod)
{
    int dad=nod;
    while(dad!=tata[dad]) dad=tata[dad];
    int cop=nod;
    while(nod!=tata[nod])
    {
        cop=nod;
        nod=tata[nod];
        tata[cop]=dad;
    }
    return dad;
}
 
void uneste(int ta, int tb)
{
    if(h[ta]>h[tb])
    {
        tata[tb]=ta;
    }
    else if(h[ta]<h[tb])
    {
        tata[ta]=tb;
    }
    else //h[ta]==h[tb]
    {
        tata[ta]=tb;
        h[tb]++;
    }
}
 
void dfs(int nod, int dest,int from)
{
    if(vizitat[nod]) return;
    vizitat[nod]=1;
    dd[nod]=from;
    if(nod == dest)
    {
        gasit=true;
        return;
    }
    if(gasit) return;
    for(auto p:vecini[nod])
    {
        int pi=p.first;
        //int cost=p.second;
        if(pi!=-1) dfs(pi,dest,nod);
    }
}
 
void sterge(int a,int b)
{
    for(int i=0; i<vecini[a].size(); i++)
    {
        if(vecini[a][i].first==b)
        {
            cost_total-=vecini[a][i].second;
            vecini[a][i]={-1,-1};
            break;
        }
    }
    for(int i=0; i<vecini[b].size(); i++)
    {
        if(vecini[b][i].first==a)
        {
            vecini[b][i]={-1,-1};
        }
    }
}
 
int main()
{
    fin>>n>>m>>k;
    for(int i=1; i<=n; i++)
    {
        tata[i]=i;
        h[i]=1;
    }
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y>>c;
        muchii.push_back({c,{x,y}});
    }
    sort(muchii.begin(),muchii.end());
    for(auto muchie: muchii)
    {
        c=muchie.first;
        x=muchie.second.first;
        y=muchie.second.second;
        int tx=tabs(x);
        int ty=tabs(y);
        if(tx!=ty)
        {
            uneste(tx,ty);
            vecini[x].push_back({y,c});
            vecini[y].push_back({x,c});
            cost_total+=c;
        }
    }
    fout<<cost_total<<"\n";
    for(int i=1; i<=k; i++)
    {
        fin>>x>>y>>c;
        gasit=false;
        memset(vizitat,0, sizeof vizitat);
        dfs(x,y,x);
        int nod=y;
        int costul=-1,nodul=-1;
        while(nod!=x)
        {
            //caut muchia nod -> dd[nod]
            for(auto p:vecini[nod])
            {
                if(costul<p.second && p.first==dd[nod])
                {
                    costul=p.second;
                    nodul=nod;
                }
            }
            nod=dd[nod];
        }
        if(costul>c)
        {
            sterge(nodul,dd[nodul]);
            cost_total+=c;
            vecini[x].push_back({y,c});
            vecini[y].push_back({x,c});
        }
        fout<<cost_total<<"\n";
    }
    return 0;
}