Cod sursă (job #641374)

#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;
    }
};

vector<pair<int,int>> 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[c].push_back({x,y});
    }

    for(int i=0;i<nmax*10;i++)
    {
        for(auto j:muchii[i])
        {
            if(getroot(j.first)!=getroot(j.second))
            {
                mergee(j.first,j.second);
                cost+=i;
                nodes[j.first].adj.push_back({j.second,i});
                nodes[j.second].adj.push_back({j.first,i});
            }
        }
    }

    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';
    }
}