Cod sursă (job #804311)

#include <bits/stdc++.h>

using namespace std;

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

struct muchie
{
    int i,j,cost;
    bool operator < (muchie x) const
    {
        return cost < x.cost;
    }
};

int n,m,k;
muchie x[100009];

int Kruskal(int cnt)
{
    int i,j,ai,aj,suma=0;
    int t[10009];
    sort(x+1,x+cnt+1);
    for(i=1;i<=n;i++)
        t[i]=i;
    for(i=1;i<=cnt;i++)
        if(t[x[i].i]!=t[x[i].j])
        {
            suma+=x[i].cost;
            ai=t[x[i].i];
            aj=t[x[i].j];
            for(j=1;j<=n;j++)
                if(t[j]==aj)
                    t[j]=ai;
        }
    return suma;
}

int main()
{
    int i,j,ai,aj,w;
    fin>>n>>m>>k;
    for(i=1;i<=m;i++)
        fin>>x[i].i>>x[i].j>>x[i].cost;
    fout<<Kruskal(m)<<"\n";
    for(i=m+1;i<=m+k;i++)
    {
        fin>>x[i].i>>x[i].j>>x[i].cost;
        fout<<Kruskal(i)<<"\n";
    }
    return 0;
}