本文主要是介绍【HDU】2860 Regroup 并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：【HDU】2860 Regroup
题目分析：其实就是披着并查集外表的模拟题，照着做就好了。。。话说题目中给了x==y。。这个真的大丈夫？。。
代码如下：
#include <cmath>
#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 )typedef long long LL ;const int MAXN = 100005 ;
const LL INF = 1e11 ;int p[MAXN] ;
LL rate[MAXN] ;
int n , m , k ;
char s[5] ;int find ( int x ) {int ans , tmp , o = x ;while ( p[o] != o )o = p[o] ;ans = o ;o = x ;while ( p[o] != o ) {tmp = p[o] ;p[o] = ans ;o = tmp ;}return ans ;
}void read ( int &x ) {x = 0 ;char c = ' ' ;while ( c < '0' || c > '9' )c = getchar () ;while ( c >= '0' && c <= '9' ) {x = x * 10 + c - '0' ;c = getchar () ;}
}void work () {int newbie , c ;int x , y ;REP ( i , n )p[i] = i , rate[i] = INF ;input () ;REP ( i , m ) {scanf ( "%s" , s ) ;if ( s[0] == 'A' ) {scanf ( "%d%d" , &newbie , &c ) ;if ( c != find ( c ) )printf ( "Reject\n" ) ;else {printf ( "Accept\n" ) ;if ( rate[c] > newbie )rate[c] = newbie ;}}if ( s[0] == 'G' ) {scanf ( "%d" , &c ) ;x = find ( c ) ;if ( x != c )printf ( "Company %d is a part of company %d.\n" , c , x ) ;else if ( rate[c] == INF )printf ( "Company %d is empty.\n" , c ) ;elseprintf ( "Lowest rate: %I64d.\n" , rate[c] ) ;}if ( s[0] == 'M' ) {scanf ( "%d%d" , &x , &y ) ;if ( x != find ( x ) || y != find ( y ) || x == y )printf ( "Reject\n" ) ;else {printf ( "Accept\n" ) ;p[y] = x ;if ( rate[x] > rate[y] )rate[x] = rate[y] ;}}}printf ( "\n" ) ;
}int main () {while ( ~scanf ( "%d%d%d" , &n , &k , &m ) )work () ;return 0 ;
}
这篇关于【HDU】2860 Regroup 并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
