学步园

传送门：【HDU】3938 Portal

题目分析：并查集离线处理即可。当然你要知道怎么计数

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REPV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define clear( a , x ) memset ( a , x , sizeof a )

const int MAXN = 10005 ;
const int MAXM = 50005 ;
const int MAXE = 10005 ;
const int INF = 0x3f3f3f3f ;

struct Edge {
	int idx , n ;
	Edge () {}
	Edge ( int __idx , int next ) :
		idx ( __idx ) ,  n ( next ) {}
} ;

struct Node {
	int u , v , c ;
	void input () {
		scanf ( "%d%d%d" , &u , &v , &c ) ;
	}
	bool operator < ( const Node &a ) const {
		return c < a.c ;
	}
} ;

Edge E[MAXE] ;
int hd[MAXM] , cntE ;
Node A[MAXM] ;
int a[MAXM] ;
int p[MAXN] ;
int num[MAXN] ;
int ask[MAXN] ;
int n , m , q ;

int find ( int x ) {
	return p[x] == x ? x : ( p[x] = find ( p[x] ) ) ;
}

void addedge ( int u , int v ) {
	E[cntE] = Edge ( v , hd[u] ) ;
	hd[u] = cntE ++ ;
}

int unique ( int a[] , int n ) {
	int cnt = 1 ;
	sort ( a + 1 , a + n + 1 ) ;
	REPF ( i , 2 , n )
		if ( a[i] != a[cnt] )
			a[++ cnt] = a[i] ;
	return cnt ;
}

int binary_search ( int x , int l , int r ) {
	while ( l < r ) {
		int m = ( l + r ) >> 1 ;
		if ( a[m] >= x )
			r = m ;
		else 
			l = m + 1 ;
	}
	return a[l] == x ? l : l - 1 ;
}

void work () {
	int cnt = 0 ;
	int ans = 0 ;
	int x , y , c ;
	cntE = 0 ;
	clear ( hd , -1 ) ;
	REPF ( i , 1 , n )
		p[i] = i , num[i] = 1 ;
	REP ( i , m ) {
		A[i].input () ;
		a[++ cnt] = A[i].c ;
	}
	cnt = unique ( a , cnt ) ;
	sort ( A , A + m ) ;
	REP ( i , q ) {
		scanf ( "%d" , &c ) ;
		addedge ( binary_search ( c , 1 , cnt + 1 ) , i ) ;
	}
	int j = 0 ;
	REPF ( i , 1 , cnt ) {
		while ( j < m && A[j].c <= a[i] ) {
			x = find ( A[j].u ) ;
			y = find ( A[j].v ) ;
			if ( x != y ) {
				ans -= num[x] * ( num[x] + 1 ) / 2 ;
				ans -= num[y] * ( num[y] + 1 ) / 2 ;
				num[y] += num[x] ;
				ans += num[y] * ( num[y] + 1 ) / 2 ;
				p[x] = y ;
			}
			++ j ;
		}
		for ( int o = hd[i] ; ~o ; o = E[o].n )
			ask[E[o].idx] = ans ;
	}
	REP ( i , q )
		printf ( "%d\n" , ask[i] ) ;
}

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