本文主要是介绍【HDU】3938 Portal 并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：【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 ;
}这篇关于【HDU】3938 Portal 并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
