Cod sursă (job #639247)

#include<cstdio>
#include<list>
#include<iterator>
#include<cstring>
#include<algorithm>
using namespace std;
FILE*in=fopen("zapada.in","r");
FILE*out=fopen("zapada.out","w");
const int NMAX=10007,MMAX=100007;
int n,m,k,i,x,y,c,ival,dad[NMAX],tnod,costdad[NMAX],deep[NMAX];
long long cost;
bool b[NMAX],activotore;
struct drum
{
    int tat,nod,val;
};
drum el,mmin,sory[MMAX];
bool sor(drum a,drum b)
{
    return a.val<b.val;
}
struct drumplus
{
    int nod,val,act;
};
drumplus ax;
list<drumplus> vec[NMAX];
list<drumplus>::iterator memit;
int fd(int x)
{
    if(dad[x]!=0)
    {
        int tat=fd(dad[x]);
        dad[x]=tat;
        return tat;
    }
    return x;
}
void app(int x,int y)
{
    int dadx=fd(x);
    int dady=fd(y);
    if(deep[dadx]>deep[dady])
    {
        dad[dady]=dadx;
    }
    else if(deep[dady]>deep[dadx])
    {
        dad[dadx]=dady;
    }
    else
    {
        dad[dady]=dadx;
        deep[dadx]++;
    }
}
void dfs(int nd)
{
    for(list<drumplus>::iterator it=vec[nd].begin();it!=vec[nd].end();it++)
    {
        if(it->act==0&&dad[it->nod]==0)
        {
            if(it->nod==ival)
            {
                activotore=1;
            }
            costdad[it->nod]=it->val;
            dad[it->nod]=nd;
            if(it->nod==ival)
            {
                activotore=1;
                return;
            }
            dfs(it->nod);
            if(activotore==1)
            {
                return;
            }
        }
    }
}
int main()
{
    fscanf(in,"%d%d%d",&n,&m,&k);
    for(i=1;i<=m;i++)
    {
        fscanf(in,"%d%d%d",&x,&y,&c);
        el.nod=y;
        el.val=c;
        el.tat=x;
        sory[i]=el;
    }
    sort(sory+1,sory+m+1,sor);
    for(i=1;i<=m;i++)
    {
        if(fd(sory[i].tat)!=fd(sory[i].nod))
        {
            ax.nod=sory[i].nod;
            ax.act=0;
            ax.val=sory[i].val;
            vec[sory[i].tat].push_back(ax);
            ax.nod=sory[i].tat;
            vec[sory[i].nod].push_back(ax);
            app(sory[i].tat,sory[i].nod);
            cost=(long long)(cost+sory[i].val);
        }
    }
    fprintf(out,"%lld\n",cost);
    for(i=1;i<=k;i++)
    {
        fscanf(in,"%d%d%d",&x,&y,&c);
        memset(dad,0,sizeof(dad));
        mmin.val=0;
        activotore=0;
        ival=y;
        dad[x]=-1;
        dfs(x);
        tnod=y;
        while(dad[tnod]!=-1)
        {
            if(mmin.val<costdad[tnod])
            {
                mmin.val=costdad[tnod];
                mmin.tat=dad[tnod];
                mmin.nod=tnod;
            }
            tnod=dad[tnod];
        }
        if(mmin.val>c)
        {
            for(list<drumplus>::iterator it=vec[mmin.tat].begin();it!=vec[mmin.tat].end();it++)
            {
                if(it->nod==mmin.nod)
                {
                    memit=it;
                }
            }
            vec[mmin.tat].erase(memit);
            for(list<drumplus>::iterator it=vec[mmin.nod].begin();it!=vec[mmin.nod].end();it++)
            {
                if(it->nod==mmin.tat)
                {
                    memit=it;
                }
            }
            vec[mmin.nod].erase(memit);
            ax.act=0;
            ax.nod=y;
            ax.val=c;
            vec[x].push_back(ax);
            ax.nod=x;
            vec[y].push_back(ax);
            cost=(long long)(cost+c);
            cost=(long long)(cost-mmin.val);
        }
        fprintf(out,"%lld\n",cost);
    }
}