Cod sursă (job #17569)

#include<stdio.h>
#include<assert.h>
#include<algorithm>
using namespace std;
struct Muchie
{
	int x,y,c;
	Muchie() {x=y=c=0;}
};
inline Muchie make(int x,int y,int c)
{
	Muchie m;
	m.x=x;m.y=y;m.c=c;
	return m;
}
class comp
{
public: inline bool operator()(const Muchie &x,const Muchie &y)
	{
		return x.c<y.c;
	}
};
int cost,n;
int t[10005];
int h[10005];
int daddy(int x)
{
	int T,aux;
	for(T=x;T!=t[T];T=t[T]);
	for(;x!=t[x];)
	{
		aux=t[x];
		t[x]=T;
		x=aux;
	}
	return T;
}
Muchie a[100005];int m;
inline void unite(int x,int y)
{
	if(h[x]==h[y])
	{
		t[x]=y;
		h[y]++;
	}
	else if(h[x]>h[y]) t[y]=x;
    else t[x]=y;
}
void apm()
{
	int u=-1;
    /*
     for(vector<Muchie>::iterator it=a.begin();it!=a.end();it++)
     fprintf(stderr,"%d %d %d\n",(*it).x,(*it).y,(*it).c);
     */
	cost=0;
	for(int i=1;i<=n;i++) t[i]=i,h[i]=1;
	for(int i=0;i<m && u<n-2;i++)
	{
		int tx=daddy(a[i].x);
		int ty=daddy(a[i].y);
		if(tx!=ty)
			cost+=a[i].c,a[++u]=a[i],unite(tx,ty);
	}
	m=u+1;
}
int main()
{
	freopen("zapada.in","r",stdin);
	freopen("zapada.out","w",stdout);
	int x,y,c,k;
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&x,&y,&c),a[i-1]=make(x,y,c);
	sort(a,a+m,comp());
	apm();
	assert(1==0);
    /*
     for(set<Muchie,comp>::iterator it=s.begin();it!=s.end();it++)
     fprintf(stderr,"%d %d %d\n",it->x,it->y,it->c);
     */
	printf("%d\n",cost);
	for(int i=1;i<=k;i++)
	{
		scanf("%d%d%d",&x,&y,&c);
		a[m++]=make(x,y,c);
		for(int i=m-1;i>0 && a[i].c<a[i-1].c;i--)
			swap(a[i],a[i-1]);
		apm();
		printf("%d\n",cost);
	}
	return 0;
}