Cod sursă (job #615372)

#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#define maxi 10000
using namespace std;
struct muchie{
   int x;
   int y;
   int cost;
};
ifstream f;
ofstream g;
vector<pair<int,int>> V[maxi+5];
vector<pair<int,int>>::iterator I,I2;
vector<muchie> v;
vector<muchie>::iterator i1,i2;
bool viz[maxi+5];
int n,m,k,a,b,c,RANG[maxi+5],R[maxi+5],tata[maxi+5],cost[maxi+5],lvl[maxi+5];
long long APM;
bool CMP(muchie A,muchie B)
{
    return(A.cost<B.cost);
}
int REP(int x)
{
    if(x==R[x])
        return x;
    else return REP(R[x]);
}
void UNIRE(int x,int y)
{
    if(RANG[x]>RANG[y])
    {
        R[y]=x;
    }
    if(RANG[y]>RANG[x])
    {
        R[x]=y;
    }
    if(RANG[x]==RANG[y])
    {
        R[y]=x;
        RANG[x]++;
    }
}
void INIT()
{
    for(int i=1;i<=n;i++)
        R[i]=i,RANG[i]=1;
}
void KRUSKAL()
{
    INIT();
    i1=v.begin();
    i2=v.end();
    sort(i1,i2,CMP);
    for(auto a:v)
    {
        int rx=REP(a.x);
        int ry=REP(a.y);
        if(rx!=ry)
        {
            UNIRE(rx,ry);
            APM+=a.cost;
            V[a.x].push_back(make_pair(a.y,a.cost));
            V[a.y].push_back(make_pair(a.x,a.cost));
        }

    }

}
void DFS(int x,int lv)
{
    viz[x]=true;
    lvl[x]=lv;
    for(auto a:V[x])
    {
        if(!viz[a.first])
        {
            tata[a.first]=x;
            cost[a.first]=a.second;
            DFS(a.first,lv+1);
        }
    }
}
void LCA(int x,int y,int&cmax,int&e1,int&e2)
{
    while(x!=y)
    {
        if(lvl[x]>lvl[y])
        {
            if(cmax<cost[x])
            {
                cmax=cost[x];
                e1=x;
                e2=tata[x];
            }
            x=tata[x];
        }
        else{
             if(cmax<cost[y])
            {
                cmax=cost[y];
                e1=y;
                e2=tata[y];
            }
            y=tata[y];
        }
    }
}
void SOLVE()
{
    f.open("zapada.in",ios::in);
    g.open("zapada.out",ios::out);
    f>>n>>m>>k;
    for(int i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        v.push_back({a,b,c});
    }
    KRUSKAL();
    g<<APM<<'\n';
    for(int i=1;i<=k;i++)
    {
        f>>a>>b>>c;
        memset(viz,0,sizeof(viz));
        memset(tata,0,sizeof(tata));
        memset(lvl,0,sizeof(lvl));
        memset(cost,0,sizeof(cost));
    DFS(1,0);
    int e1=0,e2=0,cmax=0;
    LCA(a,b,cmax,e1,e2);
    if(cmax>c)
    {
        ///elimin [e1,e2]
        ///adaug [a,b]
        I=V[e1].begin();
     for(int i=0;i<V[e1].size();i++)
   {
       if(V[e1][i].second==cmax)
        I2=I;
       I++;
   }
     V[e1].erase(I2);

     I=V[e2].begin();
     for(int i=0;i<V[e2].size();i++)
   {
       if(V[e2][i].second==cmax)
        I2=I;
       I++;
   }
     V[e2].erase(I2);
     V[a].push_back(make_pair(b,c));
     V[b].push_back(make_pair(a,c));
     APM=APM-cmax+c;
    }
    g<<APM<<'\n';
    }
}
int main()
{
    SOLVE();
    return 0;
}