记录编号	58027	评测结果	AAAAAAATTT
题目名称	危险游戏	最终得分	70
用户昵称	digital-T	是否通过	未通过
代码语言	C++	运行时间	4.512 s
提交时间	2013-04-16 11:47:57	内存使用	3.52 MiB

#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fi("tubea.in");
ofstream fo("tubea.out");
class road//地道sub[10001]
{
public:
	int pre,u,v,l;
}sub[10001];
class set//并查集的集合C
{
public:
	int count,parent;
}C[10001];
int n,t,q,a,w;
bool boo[10001];
bool op(road x,road y)//for sort sub
{
	if(x.l<y.l)return 1;
	if(x.l==y.l&&x.u<y.u)return 1;
	return 0;
}
void makeset(int x)
{
	C[x].count=1;
	C[x].parent=0;
}
int findset(int x)
{
	int y=x,z=x,tmp;
	while(C[z].parent!=0)z=C[z].parent;
	while(C[y].parent!=0)tmp=y,y=C[y].parent,C[tmp].parent=z;//路径压缩
	return z;
}
void merge(int x,int y)
{
	int e=findset(x),f=findset(y);
	if(C[e].count>C[f].count)
	{
		C[f].parent=x;
	}
	else 
	{
		if(C[e].count==C[f].count)
			C[f].count++;
		C[e].parent=y;
	}
}
int main()
{
	//================================================================INPUT
	int i,j,k;
	fi>>n>>t;
	for(i=1;i<=n;i++)makeset(i);
	for(i=1;i<=t;i++)
	{
		fi>>sub[i].u>>sub[i].v>>sub[i].l;
		sub[i].pre=i;
	}
	//=============================================================Kruskal
	sort(sub+1,sub+t+1,op);//将边按边权排序
	int sum=1,mini=sub[1].l;
	boo[1]=true;
	merge(sub[1].u,sub[1].v);//将最小边加入最小生成树中,boo将记录是否使用此边
	for(i=2;i<=t;i++)
	{
		if(sum==n-1)//边数已够
		{
			boo[i]=false;
			goto NEXT;
		}//else
		if(findset(sub[i].u)==findset(sub[i].v))
			boo[i]=false;//形成环，不使用这条边
		else
		{
			sum++;//边总量加
			mini+=sub[i].l;
			merge(sub[i].u,sub[i].v);//合并两个点的集合
			boo[i]=true;//使用了这条边
		}
		NEXT:;
	}
	fo<<mini<<endl;
	//===================================================================[1]
	fi>>q;
	for(k=1;k<=q;k++)
	{
		fi>>a>>w;
		for(i=1;i<=t;i++)//找出a的原型
			if(sub[i].pre==a)
			{
				a=i;
				break;
			}
		if(boo[a])//查询边在最小生成树中
		{
			mini=mini-sub[a].l+w;
			sub[a].l=w;
		}
		else//不在原树中,暴力！！！
		{
			for(i=1;i<=n;i++)makeset(i);
			sub[a].l=w;
			sort(sub+1,sub+t+1,op);//将边按边权排序
			sum=1,mini=sub[1].l,boo[1]=true,merge(sub[1].u,sub[1].v);//将最小边加入最小生成树中,boo将记录是否使用此边
			for(i=2;i<=t;i++)
			{
				if(sum==n-1)//边数已够
				{
					boo[i]=false;
					goto NEXT2;
				}//else
				if(findset(sub[i].u)==findset(sub[i].v))
					boo[i]=false;//形成环，不使用这条边
				else
				{
					sum++;//边总量加
					mini+=sub[i].l;
					merge(sub[i].u,sub[i].v);//合并两个点的集合
					boo[i]=true;//使用了这条边
				}
				NEXT2:;
			}
		}
		fo<<mini<<endl;
	}
	return 0;
}