Cod sursă (job #676044)

#include <bits/stdc++.h>
#define N 1007

using namespace std;


ifstream fin("zapada.in");
ofstream fout("zapada.out");

int n,m,k;
long long sol=0;
vector< pair<int,pair<int,int>> >muchii;
int a[N][N];
int father[N];
int grad[N];


int Find(int x)
{
    if( !father[x] )
        return x;
    else
    {
        int f=Find( father[x] );
        father[x]=f;
        return f;
    }
}

void Union(int x,int y)
{
    int tx=Find(x),ty=Find(y);
    if( tx!=ty )
    {
        if( grad[tx]==grad[ty] )
        {
            grad[tx]++;
            father[ty]=tx;
        }
        if( grad[tx]>grad[ty] )
        {
            father[ty]=tx;
        }
        if( grad[tx]<grad[ty] )
        {
            father[tx]=ty;
        }
    }
}


void Evaluare_muchie()
{
    int x,y,c;
    fin >> x >> y >> c;
    /// distanta de la x la ....
    vector<int> dist(N,0);
    queue<int> q;
    q.push(x);
    dist[x]=1;
    while( !q.empty() )
    {
        int cur=q.front();
        q.pop();
        for(int i=1;i<=n;i++)
            if( a[i][cur] and !dist[i] )
            {
                dist[i]=dist[cur]+1;
                q.push(i);
            }
    }
    /// reconstituire drum
    int pas=dist[y],nod=y;
    int candidatx=-1,candidaty=-1;
//cout << y << " ";
    while( nod!=x )
    {
        int aux;
        pas--;
        for(int i=1;i<=n;i++ )
            if( dist[i]==pas and a[i][nod] )
            {
                aux=i;
            }
        /// prel muchie nod-aux
        if( a[nod][aux]>c )
        {
            if( candidatx==-1 or a[candidatx][candidaty]<a[nod][aux] )
            {
                candidatx=nod;
                candidaty=aux;
            }
        }
//cout << nod << " ";
        nod=aux;
    }
//cout << "\n";

    if( candidatx!=-1 )
    {
        sol-=a[candidatx][candidaty];
        sol+=c;
        a[candidatx][candidaty]=a[candidaty][candidatx]=0;
        a[x][y]=a[y][x]=c;
    }
    fout << sol << '\n';
}

void Kruskal()
{
    sort(muchii.begin(),muchii.end());
    for(int i=0;i<m;i++)
    {
        int x= muchii[i].second.first;
        int y= muchii[i].second.second;
        int c= muchii[i].first;
        if( Find(x)!=Find(y) )
        {
            sol+=c;
            Union(x,y);

            a[x][y]=c;
            a[y][x]=c;
        }
    }
    fout << sol << '\n';
}

void Citire()
{
    fin >> n >> m >> k;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fin >> x >> y >> c;
        muchii.push_back( { c,{x,y} } );
    }
    Kruskal();
    m=n-1;
    for(int i=1;i<=k;i++)
        Evaluare_muchie();
    fin.close();
    fout.close();
}
int main()
{
    Citire();
    return 0;
}