注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

BZOJ-2816: [ZJOI2012]网络(Link Cut Tree)  

2014-06-09 19:58:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=2816


难得这道题保证了是一条链,我居然还去写LCT。。。(其实k棵splay同样可以解决问题的)


代码(边换颜色居然可以换成与之前一样的。。。):

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <set>

  •  

  • using namespace std ;

  •  

  • #define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )

  • #define rep( i , x ) for ( int i = 0 ; i ++ < x ; )

  •  

  • const int maxn = 10100 , maxc = 11 ;

  •  

  • struct link_cut_tree {

  •      

  •     #define C( t ) ( t == L( F( t ) ) )

  •      

  •     #define L( t ) left[ t ]

  •     #define R( t ) right[ t ]

  •     #define M( t ) Max[ t ]

  •     #define T( t ) Tag[ t ]

  •     #define F( t ) father[ t ]

  •     #define P( t ) parent[ splay_root( t ) ]

  •     #define G( t ) F( F( t ) )

  •     #define V( t ) value[ t ]

  •      

  •     int left[ maxn ] , right[ maxn ] , Max[ maxn ] , parent[ maxn ] , father[ maxn ] , value[ maxn ] ;

  •     bool Tag[ maxn ] ;

  •      

  •     link_cut_tree(  ) {

  •         memset( left , 0 , sizeof( left ) ) ;

  •         memset( right , 0 , sizeof( right ) ) ;

  •         memset( right , 0 , sizeof( right ) ) ;

  •         memset( parent , 0 , sizeof( parent ) ) ;

  •         memset( father , 0 , sizeof( father ) ) ;

  •         memset( Max , 0 , sizeof( Max ) ) ;

  •         memset( Tag , false , sizeof( Tag ) ) ;

  •     }

  •      

  •     inline void pushdown( int t ) {

  •         if ( T( t ) && t ) {

  •             swap( L( t ) , R( t ) ) ;

  •             T( L( t ) ) ^= true , T( R( t ) ) ^= true , T( t ) = false ;

  •         }

  •     }

  •      

  •     inline void update( int t ) {

  •         M( t ) = max( max( M( L( t ) ) , M( R( t ) ) ) , V( t ) ) ;

  •     }

  •      

  •     inline void zag( int t ) {

  •         pushdown( t ) ; pushdown( R( t ) ) ;

  •         int k = R( t ) , u = F( t ) ; bool flag = C( t ) ;

  •         update( F( R( t ) = L( k ) ) = t ) ;

  •         update( F( L( k ) = t ) = k ) ;

  •         if ( F( k ) = u ) if ( flag ) L( u ) = k ; else R( u ) = k ;

  •     }

  •      

  •     inline void zig( int t ) {

  •         pushdown( t ) ; pushdown( L( t ) ) ;

  •         int k = L( t ) , u = F( t ) ; bool flag = C( t ) ;

  •         update( F( L( t ) = R( k ) ) = t ) ;

  •         update( F( R( k ) = t ) = k ) ;

  •         if ( F( k ) = u ) if ( flag ) L( u ) = k ; else R( u ) = k ;

  •     }

  •      

  •     inline void splay( int t ) {

  •         while ( F( t ) ) {

  •             pushdown( G( t ) ) ; pushdown( F( t ) ) ; pushdown( t ) ;

  •             if ( ! G( t ) ) if ( C( t ) ) zig( F( t ) ) ; else zag( F( t ) ) ; else {

  •                 if ( C( t ) ) {

  •                     if ( C( F( t ) ) ) zig( G( t ) ) ; zig( F( t ) ) ;

  •                 } else {

  •                     if ( ! C( F( t ) ) ) zag( G( t ) ) ; zag( F( t ) ) ;

  •                 }

  •             }

  •         }

  •     }

  •      

  •     inline int splay_root( int t ) {

  •         splay( t ) ;

  •         for ( pushdown( t ) ; L( t ) ; pushdown( t = L( t ) ) ) ;

  •         return t ;

  •     }

  •      

  •     inline int Access( int t ) {

  •         int v = 0 ;

  •         do {

  •             splay( t ) ; pushdown( t ) ;

  •             F( R( t ) ) = 0 ; P( R( t ) ) = t ;

  •             update( F( R( t ) = v ) = t ) ;

  •             v = t ; t = P( t ) ;

  •         } while ( t ) ;

  •         return v ;

  •     }

  •      

  •     inline void Join( int v , int u ) {

  •         P( v ) = u ;

  •     }

  •      

  •     inline void cut( int v ) {

  •         Access( v ) ; splay( v ) ; pushdown( v ) ;

  •         F( L( v ) ) = 0 ; L( v ) = 0 ; update( v ) ; P( v ) = 0 ;

  •     }

  •      

  •     inline void Link( int v , int u ) {

  •         Access( v ) ; splay( v ) ; T( v ) ^= true ;

  •         Join( v , u ) ;

  •     }

  •      

  •     inline void Cut( int v , int u ) {

  •         Access( v ) ; int lca = Access( u ) ;

  •         if ( lca == v ) cut( u ) ; else cut( v ) ;

  •     }

  •      

  •     inline int Query( int v , int u ) {

  •         Access( v ) ; int lca = Access( u ) ;

  •         if ( lca == v ) {

  •             splay( v ) ; pushdown( v ) ;

  •             return max( V( v ) , M( R( v ) ) ) ;

  •         } else {

  •             splay( v ) ; splay( lca ) ; pushdown( lca ) ;

  •             return max( max( V( lca ) , M( R( lca ) ) ) , M( v ) ) ;

  •         }

  •     }

  •      

  •     inline void change( int v , int w ) {

  •         splay( v ) ;

  •         V( v ) = w ; update( v ) ;

  •     }

  •      

  •     inline int get_root( int v ) {

  •         Access( v ) ;

  •         return splay_root( v ) ;

  •     }

  •      

  • } lct[ maxc ] , L ;

  •  

  • int n , m , C , k ;

  •  

  • struct edge {

  •     int s , t , w ;

  •     edge( int _s , int _t , int _w ) : s( min( _s , _t ) ) , t( max( _s , _t ) ) , w( _w ) {

  •     }

  •     bool operator < ( const edge &x ) const {

  •         return s < x.s || ( s == x.s && t < x.t ) ;

  •     }

  •     bool operator == ( const edge &x ) const {

  •         return s == x.s && t == x.t ;

  •     }

  •     bool operator > ( const edge &x ) const {

  •         return s > x.s || ( s == x.s && t > x.t ) ;

  •     }

  • } ;

  • set < edge > bst ;

  •  

  • int D[ maxc ][ maxn ] ;

  •  

  • int main(  ) {

  •     memset( D , 0 , sizeof( D ) ) ;

  •     scanf( "%d%d%d%d" , &n , &m , &C , &k ) ;

  •     int val ;

  •     rep( i , n ) {

  •         scanf( "%d" , &val ) ;

  •         REP( j , 0 , ( C - 1 ) ) {

  •             lct[ j ].Max[ i ] = lct[ j ].value[ i ] = val ;

  •         }

  •     }

  •     while ( m -- ) {

  •         int s , t , w ; scanf( "%d%d%d" , &s , &t , &w ) ;

  •         lct[ w ].Link( s , t ) , bst.insert( edge( s , t , w ) ) ;

  •         D[ w ][ s ] ++ , D[ w ][ t ] ++ ;

  •     }

  •     int K = 0 ;

  •     while ( k -- ) {

  •         int a , b , c , d ; scanf( "%d" , &a ) ;

  •         if ( ! a ) {

  •             scanf( "%d%d" , &b , &c ) ;

  •             REP( j , 0 , ( C - 1 ) ) lct[ j ].change( b , c ) ;

  •         } else if ( a == 1 ) {

  •             scanf( "%d%d%d" , &b , &c , &d ) ;

  •             set < edge > :: iterator p = bst.find( edge( b , c , d ) ) ;

  •             if ( p == bst.end(  ) ) {

  •                 printf( "No such edge.\n" ) ; continue ;

  •             }

  •             if ( p -> w == d ) {

  •                 printf( "Success.\n" ) ; continue ;

  •             }

  •             if ( D[ d ][ b ] > 1 || D[ d ][ c ] > 1 ) {

  •                 printf( "Error 1.\n" ) ; continue ;

  •             }

  •             if ( lct[ d ].get_root( b ) == lct[ d ].get_root( c ) ) {

  •                 printf( "Error 2.\n" ) ; continue ;

  •             }

  •             printf( "Success.\n" ) ;

  •             lct[ p -> w ].Cut( b , c ) ; lct[ d ].Link( b , c ) ;

  •             D[ p -> w ][ b ] -- , D[ p -> w ][ c ] -- , D[ d ][ b ] ++ , D[ d ][ c ] ++ ;

  •             bst.erase( p ) ; bst.insert( edge( b , c , d ) ) ;

  •         } else {

  •             scanf( "%d%d%d" , &b , &c , &d ) ;

  •             if ( lct[ b ].get_root( c ) != lct[ b ].get_root( d ) ) {

  •                 printf( "-1\n" ) ; continue ;

  •             }

  •             printf( "%d\n" , lct[ b ].Query( c , d ) ) ;

  •         }

  •     }

  •     return 0 ;

  • }



  评论这张
 
阅读(6)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017