Cod sursă (job #662770)

#include <bits/stdc++.h>
#define nmax 10003
#define mmax 101003
using namespace std;
 
ifstream f("zapada.in");
ofstream g("zapada.out");
 
int par[nmax],h[nmax];
struct muc{
    int a,b,c;
    muc(int _a=0,int _b=0, int _c=0){
        a=_a;
        b=_b;
        c=_c;
    }
    bool operator <(muc a)
    {
        return c<a.c;
    }
};
 
muc mh[mmax];
bool del[mmax];
int n,m,k;
vector<int> adj[nmax];
 
int getpar(int a)
{
    vector<int> vis;
    while(a!=par[a])
    {
        vis.push_back(a);
        a=par[a];
    }
    for(auto e:vis) par[e]=a;
    return a;
}
 
bool merge(int a, int b)
{
    a=getpar(a);
    b=getpar(b);
    if(a==b) return 0;
    if(h[a]>h[b]) swap(a,b);
    h[b]+=h[a];
    par[a]=b;
    return 1;
}
int mspans=0;
void msp()
{
    sort(mh,mh+m);
    for(int i=1;i<=n;i++) par[i]=i;
    for(int i=0;i<m;i++)
    {
        if(merge(mh[i].a,mh[i].b))
        {
            mspans+=mh[i].c;
            adj[mh[i].a].push_back(i);
            adj[mh[i].b].push_back(i);
        }
    }
}
 
bool vis[nmax];
int findel(const int &nod, const int &lookfor)
{
    vis[nod]=1;
    for(auto i:adj[nod])
    {
        int nxt=mh[i].a==nod?mh[i].b:mh[i].a;
        if(!vis[nxt]&&!del[i])
        {
            if(nxt==lookfor)
            {
                return i;
            }
            int ed=findel(nxt,lookfor);
            if(ed!=-1)
            {
                return mh[i].c<mh[ed].c?ed:i;
            }
        }
    }
    return -1;
}
 
int main()
{
    f>>n>>m>>k;
    for(int i=0;i<m;i++)
    {
        f>>mh[i].a>>mh[i].b>>mh[i].c;
    }
    msp();
    g<<mspans<<'\n';
    for(int i=m;i<m+k;i++)
    {
        f>>mh[i].a>>mh[i].b>>mh[i].c;
        memset(vis,0,sizeof(vis));
        int rep=findel(mh[i].a,mh[i].b);
        if(mh[rep].c>mh[i].c)
        {
            mspans-=mh[rep].c;
            mspans+=mh[i].c;
            del[rep]=1;
            adj[mh[i].a].push_back(i);
            adj[mh[i].b].push_back(i);
        }
        g<<mspans<<'\n';
        
    }
    return 0;
}