Cod sursă (job #17568)

#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;
}
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();
/*
	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;
}