Cod sursă (job #17561)

#include<stdio.h>
#include<vector>
#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 daddy(int x)
{
	if(x==t[x]) 
		return t[x];
	return t[x]=daddy(t[x]);
}
vector<Muchie> a;
void apm()
{
	vector<Muchie> ans(n-1);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;
	for(vector<Muchie>::iterator it=a.begin();it!=a.end();it++)
	{
		int tx=daddy(it->x);
		int ty=daddy(it->y);
		if(tx!=ty)
			cost+=it->c,ans[++u]=*it,t[tx]=ty;
	}
	a=ans;
}
int main()
{
	freopen("zapada.in","r",stdin);
	freopen("zapada.out","w",stdout);
	int x,y,c,m,k;
	scanf("%d%d%d",&n,&m,&k);
	a.resize(m);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&x,&y,&c),a[i-1]=make(x,y,c);
	sort(a.begin(),a.end(),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.push_back(make(x,y,c));
		for(int i=a.size()-1;i>0 && a[i].c<a[i-1].c;i--)
			swap(a[i],a[i-1]);
		apm();
		printf("%d\n",cost);
	}
	return 0;
}