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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1196: [HNOI2006]公路修建问题(二分)  

2014-02-27 21:05:00|  分类: 并查集,二分判定, |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


没什么好说的,二分判定最大值,然后并查集判断连通性就好了。(之前用Kruskal弄了半版WA的我真是傻X)


代码:

  • #include <cstdio>
  • #include <algorithm>
  • #include <cstring>
  •  
  • using namespace std ;
  •  
  • #define MAXN 10010
  • #define MAXM 20010
  •  
  • int s[ MAXM ] , t[ MAXM ] , c1[ MAXM ] , c2[ MAXM ] , n , m , k ;
  •  
  • struct Uset {
  •  
  •     int father[ MAXN ] ;
  •  
  •     void Init(  ) {
  •         memset( father , 0 , sizeof( father ) ) ;
  •     }
  •  
  •     int Find( int x ) {
  •         int i = x , j = x ;
  •         for ( ; father[ i ] ; i = father[ i ] ) ;
  •         for ( ; father[ j ] ; ) {
  •             int k = father[ j ] ;
  •             father[ j ] = i ; 
  •             j = k ;
  •         }
  •         return i ;
  •     }
  •  
  •     bool check( int x , int y ) {
  •         return Find( x ) == Find( y ) ;
  •     }
  •  
  •     void Union( int x , int y ) {
  •         father[ Find( x ) ] = Find( y ) ;
  •     }
  •  
  • } u ;
  •  
  • bool Check( int x ) {
  •     u.Init(  ) ; 
  •     int cnt = 0 ; 
  •     for ( int i = 0 ; i ++ < m ; ) if ( ! u.check( s[ i ] , t[ i ] ) && c1[ i ] <= x ) {
  •         ++ cnt , u.Union( s[ i ] , t[ i ] ) ;
  •     }
  •     if ( cnt < k ) return false ;
  •     for ( int i = 0 ; i ++ < m ; ) if ( ! u.check( s[ i ] , t[ i ] ) && c2[ i ] <= x ) {
  •         u.Union( s[ i ] , t[ i ] ) , ++ cnt ;
  •     }
  •     for ( int i = 1 ; i ++ < n ; ) if ( ! u.check( i , i - 1 ) ) return false ;
  •     return true ;
  • }
  •  
  • int main(  ) {
  •     scanf( "%d%d%d" , &n , &k , &m ) ; -- m ;
  •     for ( int i = 0 ; i ++ < m ; ) scanf( "%d%d%d%d" , s + i , t + i , c1 + i , c2 + i ) ;
  •     int l = 0 , r = 30000 ;
  •     while ( r - l > 1 ) {
  •         int mid = ( l + r ) >> 1 ; 
  •         if ( Check( mid ) ) r = mid ; else l = mid ;
  •     }
  •     printf( "%d\n" , r ) ;
  •     return 0 ; 
  • }



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

历史上的今天

评论

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

页脚

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