Cod sursă (job #663128)

#include <bits/stdc++.h>
#define nmax 10005
using namespace std;
 
ifstream in("zapada.in");
ofstream out("zapada.out");
 
struct muchie
{
    int a,b,c;
    muchie(int a=0,int 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];
 
muchie maxim(const muchie a, const muchie b)
{
    if(a.c<b.c)return b;
    return a;
}
 
int f[nmax*2];
int 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<int,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(int nod, int target, muchie maxx, int d)
{
    if(nod==target)
    {
        r=maxx;
        gasit=1;
        return;
    }
    for(auto i:nodes[nod].adj)
    {
        if(!gasit&&i.first!=d)
        {
            dfs(i.first,target,maxim(maxx,muchie(nod,i.first,i.second)),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;
    in>>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;
        in>>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});
        }
    }
 
    out<<cost<<'\n';
 
    for(int i=0;i<k;i++)
    {
        int a,b,c;
        in>>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);
        }
        out<<cost<<'\n';
    }
}