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

GreenCloudS

 
 
 

日志

 
 

NOI 2008 假面舞会(DFS)  

2014-05-11 17:54:00|  分类: oi,DFS,GCD |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:http://wikioi.com/problem/1800/


这题一眼就可以看出要找环,然后搞一下GCD,不过这题的建图比较神奇,不仅要连边a->b,权值1,还要连边b->a,权值-1(这个要使劲YY一下),然后标号找环,如果没有环,把所有连通分量的最大深度加起来,ORZ LYD的神题解


代码(BZOJ挂了又要屯题了QaQ):

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <vector>

  • #include <cmath>

  •  

  • using namespace std ;

  •  

  • #define addedge( s , t , d ) E[ s ].push_back( edge( t , d ) )

  •  

  • const int maxn = 100100 , inf = 0x7fffffff ;

  •  

  • struct edge {

  •     int t , d ;

  •     edge( int _t , int _d ) : t( _t ) , d( _d ) {

  •     }

  • } ;

  • vector < edge > E[ maxn ] ;

  •  

  • int n , m , len = 0 ;

  •  

  • int gcd( int x , int y ) {

  •     if ( x < y ) swap( x , y ) ;

  •     int k ;

  •     while ( y ) {

  •         k = x % y ;

  •         x = y ;

  •         y = k ;

  •     }

  •     return x ;

  • }

  •  

  • int dfn[ maxn ] , maxd , mind ;

  • bool used[ maxn ] ;

  •  

  • void dfs( int now ) {

  •     used[ now ] = true , maxd = max( maxd , dfn[ now ] ) , mind = min( mind , dfn[ now ] ) ;

  •     for ( vector < edge > :: iterator p = E[ now ].begin(  ) ; p != E[ now ].end(  ) ; ++ p ) if ( ! used[ p -> t ] ) {

  •         dfn[ p -> t ] = dfn[ now ] + p -> d ;

  •         dfs( p -> t ) ;

  •     } else len = gcd( len , abs( dfn[ p -> t ] - ( dfn[ now ] + p -> d ) ) ) ;

  • }

  •  

  • vector < int > ve ;

  •  

  • void travel( int now ) {

  •     dfn[ now ] = 1 , ve.push_back( now ) ;

  •     for ( vector < edge > :: iterator p = E[ now ].begin(  ) ; p != E[ now ].end(  ) ; ++ p ) if ( ! dfn[ p -> t ] ) travel( p -> t ) ;

  • }

  •  

  • int ans = 0 ;

  •  

  • int main(  ) {

  •     freopen( "input.txt" , "r" , stdin ) ;

  •     freopen( "output.txt" , "w" , stdout ) ;

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

  •     while ( m -- ) {

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

  •         addedge( s , t , 1 ) , addedge( t , s , -1 ) ;

  •     }

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

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

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

  •         dfn[ i ] = 1 , maxd = - inf , mind = inf ;

  •         dfs( i ) ;

  •         ans += maxd - mind + 1 ;

  •     }

  •     if ( len ) {

  •         if ( len < 3 ) printf( "-1 -1\n" ) ; else {

  •             int x = inf , y = sqrt( len ) ;

  •             for ( int i = 0 ; i ++ < y ; ) if ( ! ( len % i ) ) {

  •                 if ( i >= 3 ) x = min( x , i ) ;

  •                 if ( len / i >= 3 ) x = min( x , len / i ) ;

  •             }

  •             printf( "%d %d\n" , len , x ) ;

  •         }

  •     } else {

  •         if ( ans < 3 ) printf( "-1 -1\n" ) ; else printf( "%d 3\n" , ans ) ;

  •     }

  •     return 0 ;

  • }


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

历史上的今天

评论

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

页脚

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