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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1006: [HNOI2008]神奇的国度(弦图的最小染色,完美消除序列最大势算法)  

2014-02-25 19:24:00|  分类: oi,bzoj,弦图,MCS |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

代码:http://www.lydsy.com/JudgeOnline/problem.php?id=1006


弦图的最小染色,详见CDQ的09年WC论文《弦图与区间图》。


代码:

  • #include <cstdio>
  • #include <algorithm>
  • #include <cstring>
  •  
  • using namespace std ;
  •  
  • #define AddEdge( s , t ) Add( s , t ) , Add( t , s )
  • #define MAXN 10100
  • #define inf 0x7fffffff
  •  
  • struct edge {
  •         edge *next ;
  •         int t ;
  • } *head[ MAXN ] ;
  •  
  • void Add( int s , int t ) {
  •         edge *p = new( edge ) ;
  •         p -> t = t , p -> next = head[ s ] ;
  •         head[ s ] = p ;
  • }
  •  
  • int n , m , ans = 0 , c[ MAXN ] , l[ MAXN ] ;
  • bool f[ MAXN ] , F[ MAXN ] ;
  •  
  • int main(  ) {
  •         scanf( "%d%d" , &n , &m ) ;
  •         memset( head , 0 , sizeof( head ) ) ;
  •         while ( m -- ) {
  •                int s , t ; scanf( "%d%d" , &s , &t ) ;
  •                AddEdge( s , t ) ;
  •         }
  •         memset( f , false , sizeof( f ) ) ;
  •         memset( l , 0 , sizeof( l ) ) ;
  •         for ( int i = 0 ; i ++ < n ; ) {
  •                int rec = - inf , ret ;
  •                for ( int j = 0 ; j ++ < n ; ) if ( ! f[ j ] && l[ j ] > rec ) {
  •                        rec = l[ j ] , ret = j ;
  •                }
  •                for ( int j = 0 ; j ++ < n ; ) F[ j ] = true ;
  •                f[ ret ] = true ;
  •                for ( edge *p = head[ ret ] ; p ; p = p -> next ) if ( ! f[ p -> t ] ) {
  •                        l[ p -> t ] ++ ;
  •                } else {
  •                        F[ c[ p -> t ] ] = false ;
  •                }
  •                for ( int j = 0 ; j ++ < n ; ) if ( F[ j ] ) {
  •                        c[ ret ] = j , ans = max( ans , j ) ;
  •                        break ;
  •                }
  •         }
  •         printf( "%d\n" , ans ) ;
  •         return 0 ;
  • }



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

历史上的今天

评论

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

页脚

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