Cod sursă (job #17560)

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