Cod sursă (job #663117)

#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;
} 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].adj.erase(find(nodes[a.a].adj.begin(),nodes[a.a].adj.end(),{a.b,a.c});
    nodes[a.b].adj.erase(find(nodes[a.b].adj.begin(),nodes[a.b].adj.end(),{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;
    
    for(int i=0;i<k;i++)
    {
        int a,b,c;
        in>>a>>b>>c;
        cost+=c;
        gasit=0;
        dfs(a,b,muchie(a,b,c),-1);
        muchie tmp=r;
        cost-=tmp.c;
    }
}