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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1093: [ZJOI2007]最大半连通子图(Tarjan缩SCC+拓扑DP)  

2014-01-28 21:31:00|  分类: DAG,oi,bzoj,scc, |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


首先缩SCC,然后每个SCC的权就是该SCC的大小,那么最大半连通子图就是图上的一条最长链,那么就在DAG上搞两次拓扑排序就可以啦~

为了防止第二问出错,记得判重边(我偷懒用了SET,感觉越来越依赖STL了。。。)


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <stack>

  • #include <set>

  •  

  • using namespace std ;

  •  

  • #define MAXM 1001000

  • #define MAXN 100100

  •  

  • struct edge {

  •     edge *next ;

  •     int t ;

  • } *head[ MAXN ] ;

  •  

  • int n , m , MAX ;

  •  

  • void AddEdge( int s , int t ) {

  •     edge *p = new( edge ) ;

  •     p -> t = t , p -> next = head[ s ] ;

  •     head[ s ] = p ;

  • }

  •  

  • struct EDGE {

  •     int s , t ;

  •     bool operator < ( const EDGE &a ) const {

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

  •     }

  •     bool operator == ( const EDGE &a ) const {

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

  •     }

  •     bool operator > ( const EDGE &a ) const {

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

  •     }

  • } E[ MAXM ] ;

  •  

  • void Init(  ) {

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

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

  •     for ( int i = 0 ; i ++ < m ; ) {

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

  •         E[ i ].s = s , E[ i ].t = t ;

  •     }

  • }

  •  

  • int dfn[ MAXN ] , low[ MAXN ] , scc[ MAXN ] , Index = 0 , size[ MAXN ] ;

  • stack < int > Stack ;

  • bool f[ MAXN ] ;

  •  

  • void dfs( int v ) {

  •     Stack.push( v ) , f[ v ] = true , dfn[ v ] = low[ v ] = ++ Index ;

  •     for ( edge *p = head[ v ] ; p ; p = p -> next ) if ( ! dfn[ p -> t ] ) {

  •         dfs( p -> t ) ; low[ v ] = min( low[ v ] , low[ p -> t ] ) ;

  •     } else if ( f[ p -> t ] ) low[ v ] = min( low[ v ] , low[ p -> t ] ) ;

  •     if ( low[ v ] == dfn[ v ] ) {

  •         size[ v ] = 0 ;

  •         int u ;

  •         do {

  •             u = Stack.top(  ) ; Stack.pop(  ) , f[ u ] = false ;

  •             size[ scc[ u ] = v ] ++ ;

  •         } while ( u != v ) ;

  •     }

  • }

  •  

  • set < EDGE > S ;

  • int NUM[ MAXN ] ;

  •  

  • EDGE make( int s , int t ) {

  •     EDGE u ;

  •     u.s = s , u.t = t ;

  •     return u ;

  • }

  •  

  • void Tarjan(  ) {

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

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

  •     for ( int i = 0 ; i ++ < n ; ) if ( ! dfn[ i ] ) {

  •         dfs( i ) ;

  •     }

  •     S.clear(  ) ;

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

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

  •     for ( int i = 0 ; i ++ < m ; ) if ( scc[ E[ i ].s ] != scc[ E[ i ].t ] ) {

  •         EDGE u = make( scc[ E[ i ].s ] , scc[ E[ i ].t ] ) ;

  •         if ( S.find( u ) == S.end(  ) ) {

  •             S.insert( u ) , AddEdge( u.s , u.t ) ;

  •             NUM[ u.t ] ++ ;

  •         }

  •     }

  • }

  •  

  • int dp[ MAXN ] , ans = 0 , num[ MAXN ] ;

  •  

  • void Dp(  ) {

  •     for ( int i = 0 ; i ++ < n ; ) num[ i ] = NUM[ i ] ;

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

  •     while ( ! Stack.empty(  ) ) Stack.pop(  ) ;

  •     for ( int i = 0 ; i ++ < n ; ) if ( i == scc[ i ] && ! num[ i ] ) {

  •         Stack.push( i ) , dp[ i ] = size[ i ] ;

  •     }

  •     while ( ! Stack.empty(  ) ) {

  •         int v = Stack.top(  ) ; Stack.pop(  ) ;

  •         for ( edge *p = head[ v ] ; p ; p = p -> next ) {

  •             dp[ p -> t ] = max( dp[ p -> t ] , dp[ v ] + size[ p -> t ] ) ;

  •             if ( ! ( -- num[ p -> t ] ) ) Stack.push( p -> t ) ;

  •         }

  •     }

  •     for ( int i = 0 ; i ++ < n ; ) ans = max( ans , dp[ i ] ) ;

  • }

  •  

  • int cnt[ MAXN ] , Cnt = 0 ;

  •  

  • void Count(  ) {

  •     for ( int i = 0 ; i ++ < n ; ) num[ i ] = NUM[ i ] ;

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

  •     while ( ! Stack.empty(  ) ) Stack.pop(  ) ;

  •     for ( int i = 0 ; i ++ < n ; ) if ( i == scc[ i ] && ! num[ i ] ) {

  •         Stack.push( i ) , cnt[ i ] = 1 ;

  •     }

  •     while ( ! Stack.empty(  ) ) {

  •         int v = Stack.top(  ) ; Stack.pop(  ) ;

  •         for ( edge *p = head[ v ] ; p ; p = p -> next ) {

  •             if ( dp[ p -> t ] == dp[ v ] + size[ p -> t ] ) cnt[ p -> t ] += cnt[ v ] , cnt[ p -> t ] %= MAX ;

  •             if ( ! ( -- num[ p -> t ] ) ) Stack.push( p -> t ) ;

  •         }

  •     }

  •     for ( int i = 0 ; i ++ < n ; ) if ( ans == dp[ i ] ) Cnt += cnt[ i ] , Cnt %= MAX ;

  • }

  •  

  • int main(  ) {

  •     Init(  ) ;

  •     Tarjan(  ) ;

  •     Dp(  ) ;

  •     Count(  ) ;

  •     printf( "%d\n%d\n" , ans , Cnt ) ;

  •     return 0 ;

  • }


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

历史上的今天

评论

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

页脚

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