记录编号	129798	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HNOI 2010]城市建设	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	9.738 s
提交时间	2014-10-20 22:23:06	内存使用	1.27 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int SIZEN=50100;
typedef long long LL;
class UFS{
public:
	int fa[SIZEN];
	void init(int n){for(int i=0;i<=n;i++) fa[i]=i;}
	int grand(int x){
		return fa[x]==x?x:fa[x]=grand(fa[x]);
	}
	bool merge(int a,int b){
		int ga=grand(a),gb=grand(b);
		if(ga==gb) return false;
		fa[ga]=gb;
		return true;
	}
}ufs;
class EDGE{
public:
	int id;
	int u,v,cost;
	bool del,uni;
	EDGE(){id=u=v=cost=del=uni=0;}
};
bool operator < (EDGE a,EDGE b){
	return a.cost<b.cost;
}
class OPT{
public:
	int id;
	int cost;
};
OPT ops[SIZEN];
int N,M,Q;
LL ans[SIZEN];
vector<EDGE> E;
void read(void){
	scanf("%d%d%d",&N,&M,&Q);
	EDGE e;
	for(int i=1;i<=M;i++){
		scanf("%d%d%d",&e.u,&e.v,&e.cost);
		e.id=i;
		E.push_back(e);
	}
	for(int i=1;i<=Q;i++){
		OPT &q=ops[i];
		scanf("%d%d",&q.id,&q.cost);
	}
}
void solve(int l,int r,vector<EDGE> E,int n,LL sum,int upd_l,int upd_r){
	map<int,int> lis;
	if(l==r) upd_r=r;
	//进行更新
	for(int i=0;i<E.size();i++) lis.insert(make_pair(E[i].id,i));
	for(int i=upd_l;i<=upd_r;i++){
		OPT &q=ops[i];
		if(lis.count(q.id)){
			int p=lis[q.id];
			E[p].cost=q.cost;
		}
	}
	//将边按照权值排序
	sort(E.begin(),E.end());
	//只剩下了一个询问,暴力求当前可行边集
	if(l==r){
		ufs.init(n+10);
		for(int i=0;i<E.size();i++){
			EDGE &e=E[i];
			if(ufs.merge(e.u,e.v)) sum+=e.cost;
		}
		ans[l]=sum;
		return;
	}
	set<int> es;//把l~r之间操作的边扔进去
	for(int i=l;i<=r;i++) es.insert(ops[i].id);
	//R操作,去掉一些边
	/*这次,将l~r之间询问边的边权赋为无穷大,那么E中不在MST中的边,
	必不在l~r间任一查询答案的MST中*/
	ufs.init(n+10);
	for(int i=0;i<E.size();i++){
		EDGE &e=E[i];
		if(es.count(e.id)) continue;//跳过询问边,相当于将边权赋为无穷大
		if(!ufs.merge(e.u,e.v)) e.del=true;
	}
	//C操作,收缩一些点
	/*这次,将l~r之间询问边的边权设为无穷小,那么E中在MST中的边,
	必然在l~r间任一查询答案的MST中
	*/
	ufs.init(n+10);
	for(int i=0;i<E.size();i++){//先期插入所有询问边,相当于将边权赋为无穷小
		EDGE &e=E[i];
		if(es.count(e.id)) ufs.merge(e.u,e.v);
	}
	for(int i=0;i<E.size();i++){
		EDGE &e=E[i];
		if(es.count(e.id)||e.del) continue;
		if(ufs.merge(e.u,e.v)) e.uni=true,sum+=e.cost;//该边一定在l~r所有查询答案的MST中
	}
	//重新给点标号,建出新图,自然会扔掉一些边
	ufs.init(n+10);
	for(int i=0;i<E.size();i++) if(E[i].uni) ufs.merge(E[i].u,E[i].v);//缩点
	map<int,int> mp;int tot=0;
	for(int i=1;i<=n;i++){//给未缩的点编号
		int g=ufs.grand(i);
		if(g==i) mp[i]=++tot;
	}
	vector<EDGE> new_E;
	for(int i=0;i<E.size();i++){
		EDGE e=E[i];
		if(e.del||e.uni) continue;//一定在和一定不在答案中的边不会被纳入考虑
		e.u=mp[ufs.grand(e.u)],e.v=mp[ufs.grand(e.v)];
		new_E.push_back(e);
	}
	int mid=(l+r)/2;
	solve(l,mid,new_E,tot,sum,l,0);
	solve(mid+1,r,new_E,tot,sum,l,mid);
}
int main(){
	freopen("hnoi2010_city.in","r",stdin);
	freopen("hnoi2010_city.out","w",stdout);
	read();
	solve(1,Q,E,N,0,1,0);
	for(int i=1;i<=Q;i++) printf("%lld\n",ans[i]);
	return 0;
}