Cod sursă (job #663130)

#include <bits/stdc++.h>
#define nmax 10005
using namespace std;
 
FILE *in=fopen("zapada.in","r");
FILE *out=fopen("zapada.out","w");
 
struct muchie
{
    int16_t a,b;
    int c;
    muchie(int16_t a=0,int16_t b=0,int c=0)
    {
        this->a=a;
        this->b=b;
        this->c=c;
    }
    bool operator <(const muchie other)
    {
        return c<other.c;
    }
    void output()
    {
        cout<<a<<' '<<b<<' '<<c<<'\n';
    }
    bool operator ==(const muchie other)
    {
        return a==other.a&&b==other.b&&c==other.c;
    }
} muchii[10*nmax];
 
void maxim(const muchie &A, int &a, int &b, int &c)
{
    if(A.c<c)
    {
        A.a=a;
        A.b=b;
        A.c=c;
    }
}
 
int16_t f[nmax*2];
int8_t h[nmax*2];
 
int getroot(int nod)
{
    if(!f[nod])return nod;
    int tmp=getroot(f[nod]);
    f[nod]=tmp;
    return tmp;
}
 
void mergee(int a, int b)
{
    if(h[a]>h[b])
    {
        f[getroot(b)]=getroot(a);
    }
    else
    {
        f[getroot(a)]=getroot(b);
        h[getroot(b)]+=(h[getroot(b)]==h[getroot(a)]);
    }
}
 
struct node
{
    vector<pair<int16_t,int>> adj;
    void rem(int nod,int cost)
    {
        for(auto it=adj.begin();it!=adj.end();it++)
        {
            if((*it).first==nod&&(*it).second==cost)
            {
                adj.erase(it);
                return;
            }
        }
    }
} nodes[nmax];
 
muchie r;
bool gasit=0;
 
void dfs(int16_t nod, int16_t target, int16_t d)
{
    if(nod==target)
    {
        gasit=1;
        return;
    }
    for(auto i:nodes[nod].adj)
    {
        if(!gasit&&i.first!=d)
        {
            maxim(r,nod,i.first,i.second);
            dfs(i.first,target,nod);
        }
    }
}
 
void add(muchie a)
{
    nodes[a.a].adj.push_back({a.b,a.c});
    nodes[a.b].adj.push_back({a.a,a.c});
}
 
void rem(muchie a)
{
    nodes[a.a].rem(a.b,a.c);
    nodes[a.b].rem(a.a,a.c);
}
 
int main()
{
    int n,m,k;
    fscanf(in,"%i %i %i",&n,&m,&k);
    for(int i=1;i<=n;i++)
    {
        f[i]=i+n;
    }
 
    int cost=0;
 
    for(int i=0;i<m;i++)
    {
        int x,y,c;
        fscanf(in,"%i %i %i",&x,&y,&c);
        muchii[i]=muchie(x,y,c);
    }

    sort(muchii,muchii+m);
 
    for(int i=0;i<m;i++)
    {
        if(getroot(muchii[i].a)!=getroot(muchii[i].b))
        {
            mergee(muchii[i].a,muchii[i].b);
            cost+=muchii[i].c;
            nodes[muchii[i].a].adj.push_back({muchii[i].b,muchii[i].c});
            nodes[muchii[i].b].adj.push_back({muchii[i].a,muchii[i].c});
        }
    }
 
    fprintf(out,"%i\n",cost);
 
    for(int i=0;i<k;i++)
    {
        int a,b,c;
        fscanf(in,"%i %i %i",&a,&b,&c);
        cost+=c;
        gasit=0;
        muchie ttmp=muchie(a,b,c);
        dfs(a,b,ttmp,-1);
        muchie tmp=r;
        cost-=tmp.c;
        if(!(ttmp==tmp))
        {
            rem(tmp);
            add(ttmp);
        }
        fprintf(out,"%i\n",cost);
    }
}