Cod sursă (job #639250)

#include<cstdio>
#include<vector>
#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;
drumplus vec[NMAX][NMAX];
int it[NMAX];
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(int t=0;t<it[nd];t++)
    {
        if(vec[nd][t].act==0&&dad[vec[nd][t].nod]==0)
        {
            if(vec[nd][t].nod==ival)
            {
                activotore=1;
            }
            costdad[vec[nd][t].nod]=vec[nd][t].val;
            dad[vec[nd][t].nod]=nd;
            if(vec[nd][t].nod==ival)
            {
                activotore=1;
                return;
            }
            dfs(vec[nd][t].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][it[sory[i].tat]]=ax;
            it[sory[i].tat]++;
            ax.nod=sory[i].tat;
            vec[sory[i].nod][it[sory[i].nod]]=ax;
            it[sory[i].nod]++;
            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(int t=0;t<it[mmin.tat];t++)
            {
                if(vec[mmin.tat][t].nod==mmin.nod)
                {
                    vec[mmin.tat][t].act=1;
                }
            }
            for(int t=0;t<it[mmin.nod];t++)
            {
                if(vec[mmin.nod][t].nod==mmin.tat)
                {
                    vec[mmin.nod][t].act=1;
                }
            }
            ax.act=0;
            ax.nod=y;
            ax.val=c;
            vec[x][it[x]]=ax;
            it[x]++;
            ax.nod=x;
            vec[y][it[y]]=ax;
            it[y]++;
            cost=(long long)(cost+c);
            cost=(long long)(cost-mmin.val);
        }
        fprintf(out,"%lld\n",cost);
    }
}