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

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
const int MAXN=5e4+100;
struct ufs_{
	int fa[MAXN];
	void init(int n){ for(int i=0;i<=n;i++) fa[i]=i; }
	int get_fa(int n){
		if(fa[n]!=n) fa[n]=get_fa(fa[n]);
		return fa[n];
	}
	bool uni(int a,int b){
		int af=get_fa(a);
		int bf=get_fa(b);
		if(af==bf) return false;
		fa[af]=bf;
		return true;
	}
}ufs;

struct edge{
	int u,v;
	int cost;
	int id;
	bool rem,uni;
	edge(){ u=v=cost=id=0; uni=rem=false;}
	bool operator < (const edge & e)const{
		return cost<e.cost;
	}
};

struct query{
	int id;
	int cost;
}querys[MAXN];

int N,M,Q;
LL Ans[MAXN];
vector<edge> ES;

void init(){
	scanf("%d %d %d",&N,&M,&Q);
	for(int i=1;i<=M;i++){
		edge e; scanf("%d %d %d",&e.u,&e.v,&e.cost);
		e.id=i;
		ES.push_back(e);
	}
	for(int i=1;i<=Q;i++){
		query & q=querys[i];
		scanf("%d %d",&q.id,&q.cost);
	}
}

bool isinset(int n,set<int> & s){
	return s.find(n)!=s.end();
}

void solve(int left,int right,vector<edge> E,int n,LL sum,int upd_left,int upd_right){
	
	//把之前的更新给更新了 
	map<int,int> e2q; 
	if(left==right) upd_right=right;
	for(int i=0;i<E.size();i++)
		e2q.insert(make_pair(E[i].id,i));
	for(int i=upd_left;i<=upd_right;i++){
		query & q=querys[i];
		if(e2q.find(q.id)!=e2q.end()){
			int p=e2q[q.id];
			E[p].cost=q.cost;
		}
	}


	sort(E.begin(),E.end());
	
	//暴力 
	if(left==right){
		ufs.init(n+10);
		for(int i=0;i<E.size();i++){
			edge & e=E[i];
			if(ufs.uni(e.u,e.v)) sum+=e.cost;
		}
		Ans[left]=sum;
		return;
	}
	
	//es里面存的是left,right之间操作的边...
	set<int> es;
	for(int i=left;i<=right;i++)
		es.insert(querys[i].id);
	
	//扔边 
	ufs.init(n+10);
	for(int i=0;i<E.size();i++){
		edge & e=E[i];
		if(isinset(e.id,es)) continue;
		if(ufs.uni(e.u,e.v)==false)
			e.rem=true;
	}
	
	//缩点 
	ufs.init(n+10);
	for(int i=0;i<E.size();i++){
		edge & e=E[i];
		if(isinset(e.id,es)) ufs.uni(e.u,e.v);
	}
	for(int i=0;i<E.size();i++){
		edge & e=E[i];
		if(isinset(e.id,es) || e.rem)continue;
		if(ufs.uni(e.u,e.v)) e.uni=true,sum+=e.cost;
	}
	
	//重建 
	ufs.init(n+10);
	for(int i=0;i<E.size();i++){
		if(E[i].uni) ufs.uni(E[i].u,E[i].v);
	}
	map<int,int> m;int tn=0;
	for(int i=1;i<=n;i++){
		int fa=ufs.get_fa(i);
		if(fa==i) m[i]=++tn;
	}
	vector<edge> new_e;
	for(int i=0;i<E.size();i++){
		edge e=E[i];
		if(e.rem || e.uni) continue;
		e.u=m[ufs.get_fa(e.u)]; e.v=m[ufs.get_fa(e.v)];
		new_e.push_back(e);
	}
	
	int mid=(left+right)/2;
	solve(left,mid,new_e,tn,sum,left,0);
	solve(mid+1,right,new_e,tn,sum,left,mid);
}

int main(){
	freopen("hnoi2010_city.in","r",stdin);
	freopen("hnoi2010_city.out","w",stdout);
	init();
	solve(1,Q,ES,N,0,1,0);
	for(int i=1;i<=Q;i++)
		printf("%lld\n",Ans[i]);
	return 0;
}