Cod sursă (job #17567)

#include<stdio.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];
inline 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;
}
char s[50];
void parse(int &x,int &y,int &z)
{
	fgets(s,20,stdin);
	int ind;
	
	x=0;
	for(ind=0;s[ind]!=' ';ind++)
		x=x*10+s[ind]-'0';
	y=0;
	for(ind=ind+1;s[ind]!=' ';ind++)
		y=y*10+s[ind]-'0';
	z=0;
	for(ind=ind+1;s[ind]!='\n';ind++)
		z=z*10+s[ind]-'0';
}
int main()
{
	freopen("zapada.in","r",stdin);
	freopen("zapada.out","w",stdout);
	int x,y,c,k;
	parse(n,m,k);
	for(int i=1;i<=m;i++)
		parse(x,y,c),a[i-1]=make(x,y,c);
	sort(a,a+m,comp());
	apm();
/*
	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;
}