Cod sursă (job #269021)

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

#define NMax 10005
#define MMax 100005

using namespace std;

ifstream fin("zapada.in");
ofstream fout("zapada.out");

int N,M,K;
struct Edges{
    int x,y,z;
} Edge[MMax];
int state[NMax],father[NMax];
int totalCost;

void Read();

inline bool cmp(Edges a,Edges b)
{
    return a.z<b.z;
}

int GetRoot(int root)
{
    for(;root!=father[root];root=father[root]);
    return root;
}

void Unite(int x,int y)
{
    if(state[x]>state[y])
        father[y]=x;
    else
        father[x]=y;
    if(state[x]==state[y])
        state[y]++;
}

void APM()
{
    for(int i=1;i<=M;i++)
    {
        int x=Edge[i].x;
        int y=Edge[i].y;
        int rootx=GetRoot(x);
        int rooty=GetRoot(y);
        if(rootx!=rooty)
        {
            Unite(rootx,rooty);
            totalCost+=Edge[i].z;
        }
    }
}

int main()
{
    Read();
    for(int i=1;i<=N;i++)
        state[i]=father[i]=i;
    sort(Edge+1,Edge+M+1,cmp);
    APM();
    fout<<totalCost<<"\n";

    while(K--)
    {
        for(int i=1;i<=N;i++)
            state[i]=father[i]=i;
        M++;
        fin>>Edge[M].x>>Edge[M].y>>Edge[M].z;
        sort(Edge+1,Edge+M+1,cmp);
        totalCost=0;
        APM();
        fout<<totalCost<<"\n";
    }

    return 0;
}

void Read()
{
    fin>>N>>M>>K;
    for(int i=1;i<=M;i++)
        fin>>Edge[i].x>>Edge[i].y>>Edge[i].z;
}