学步园

传送门：【BZOJ】2001  [Hnoi2010]City 城市建设

题目分析：今天一中午+一下午的时间全部交代给这题了。。。

代码如下：

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std ;
 
#define REP( i , a , b ) for ( int i = ( a ) ; i <  ( b ) ; ++ i )
#define FOR( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define REV( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next )
#define CLR( a , x ) memset ( a , x , sizeof a )
#define CPY( a , x ) memcpy ( a , x , sizeof a )
#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define root 1 , 1 , cnt
#define mid ( ( l + r ) >> 1 )

typedef long long LL ;

const int MAXN = 20005 ;
const int MAXM = 50005 ;
const int MAXQ = 50005 ;
const int INF = 0x3f3f3f3f ;

struct Edge {
	int u , v , d ;
	int idx ;
	bool operator < ( const Edge& a ) const {
		return d < a.d ;
	}
} E[17][MAXM] , L[MAXM] , tmp[MAXM] ;//E[][]层次图，L为当前层次的图，tmp为中间变量

struct ASK {
	int k , d ;
} ask[MAXQ] ;//询问

int edge_num[17] , node_num[17] ;//每一层点和边的数量
bool change[MAXM] ;//change[] = 1则该边是必须在最小生成树内的边
int newv[MAXN] ;//点的新标号
int real[MAXM] ;//将边的编号转化为改变后的编号
int p[MAXN] , rank[MAXN] ;//并查集专用
int val[MAXM] ;//边的价值
LL ans[MAXQ] ;//答案
int n , m , q ;

int find ( int x ) {
	int o = x , ans , tmp ;
	while ( o != p[o] ) o = p[o] ;
	ans = o , o = x ;
	while ( o != p[o] ) {
		tmp = p[o] ;
		p[o] = ans ;
		o = tmp ;
	}
	return ans ;
}

bool merge ( int x , int y ) {//合并return 1，否则return 0
	x = find ( x ) ;
	y = find ( y ) ;
	if ( x == y ) return 0 ;
	if ( rank[x] <= rank[y] ) {
		p[x] = y ;
		if ( rank[x] == rank[y] ) ++ rank[y] ;
	} else p[y] = x ;
	return 1 ;
}

void clear ( int n ) {
	FOR ( i , 1 , n ) p[i] = i , rank[i] = 0 ;
}

void contraction ( int& NV , int& NE , LL& res ) {
	int NV_2 = 0 , NE_2 = 0 ;
	clear ( NV ) ;
	REP ( i , 0 , NE ) change[i] = 0 ;
	sort ( L , L + NE ) ;
	REP ( i , 0 , NE ) {
		if ( merge ( L[i].u , L[i].v ) && L[i].d != -INF ) {//必须在树中的边
			res += L[i].d ;
			change[i] = 1 ;
		} else tmp[NE_2 ++] = L[i] ;
	}
	clear ( NV ) ;
	REP ( i , 0 , NE ) if ( change[i] ) merge ( L[i].u , L[i].v ) ;
	FOR ( i , 1 , NV ) if ( find ( i ) == i ) newv[i] = ++ NV_2 ;//点重标号
	FOR ( i , 1 , NV ) newv[i] = newv[find ( i )] ;
	REP ( i , 0 , NE_2 ) {
		L[i] = tmp[i] ;
		real[L[i].idx] = i ;//修改边的实际对应编号
		L[i].u = newv[L[i].u] ;
		L[i].v = newv[L[i].v] ;
	}
	NV = NV_2 ;
	NE = NE_2 ;
}

void reduction ( int& NV , int& NE ) {
	int NE_2 = 0 ;
	clear ( NV ) ;
	sort ( L , L + NE ) ;
	REP ( i , 0 , NE ) if ( merge ( L[i].u , L[i].v ) || L[i].d == INF ) {//保存可以变成树边的边
		real[L[i].idx] = NE_2 ;//修改边的实际对应编号
		L[NE_2 ++] = L[i] ;
	}
	NE = NE_2 ;
}

void cdq_solve ( int l , int r , int cur , LL res ) {
	int NV = node_num[cur] ;//当前层次图的点数
	int NE = edge_num[cur] ;//当前层次图的边数
	if ( l == r ) val[ask[l].k] = ask[l].d ;//修改边权
	REP ( i , 0 , NE ) {
		E[cur][i].d = val[E[cur][i].idx] ;
		L[i] = E[cur][i] ;
		real[L[i].idx] = i ;
	}
	if ( l == r ) {//只有一个查询操作，直接MST求解
		clear ( NV ) ;
		sort ( L , L + NE ) ;
		REP ( i , 0 , NE ) if ( merge ( L[i].u , L[i].v ) ) res += L[i].d ;
		ans[l] = res ;
		return ;
	}
	FOR ( i , l , r ) L[real[ask[i].k]].d = -INF ;
	contraction ( NV , NE , res ) ;//将必须在最小生成树内的边缩去
	FOR ( i , l , r ) L[real[ask[i].k]].d =  INF ;
	reduction ( NV , NE ) ;//将一定不在最小生成树内的边删除
	node_num[cur + 1] = NV ;//保存下一层次图的点数
	edge_num[cur + 1] = NE ;//保存下一层次图的边数
	REP ( i , 0 , NE ) E[cur + 1][i] = L[i] ;//建立下一层次图
	int m = ( l + r ) >> 1 ;
	cdq_solve ( l , m , cur + 1 , res ) ;
	cdq_solve ( m + 1 , r , cur + 1 , res ) ;
}

void solve () {
	REP ( i , 0 , m ) {
		scanf ( "%d%d%d" , &E[0][i].u , &E[0][i].v,  &E[0][i].d ) ;
		val[i] = E[0][i].d ;
		E[0][i].idx = i ;
	}
	FOR ( i , 1 , q ) {
		scanf ( "%d%d" , &ask[i].k , &ask[i].d ) ;
		-- ask[i].k ;
	}
	node_num[0] = n ;
	edge_num[0] = m ;
	cdq_solve ( 1 , q , 0 , 0 ) ;
	FOR ( i , 1 , q ) printf ( "%lld\n" , ans[i] ) ;
}

int main () {
	scanf ( "%d%d%d" , &n , &m , &q ) ;
	solve () ;
	return 0 ;
}