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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1486: [HNOI2009]最小圈(二分判定+DFS查负权圈)  

2014-02-03 14:04:00|  分类: oi,bzoj,二分,DFS |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


二分判定最小平均值,如果我们枚举一个端点mid,我们对所有边权减去mid,如果存在负权圈,那么就说明存在比枚举值更小的平均值,反之不存在,然后二分即可。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

  • #define esp 0.0000000001

  • #define MAXN 3010

  •  

  • const double inf = double( 0x7fffffff ) * double( 0x7fffffff ) ;

  •  

  • struct edge {

  •     edge *next ;

  •     int t ;

  •     double d ;

  •     edge(  ) {

  •         next = NULL ;

  •     }

  • } *head[ MAXN ] ;

  •  

  • int n , m ;

  •  

  • void AddEdge( int s , int t , double d ) {

  •     edge *p = new( edge ) ;

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

  •     head[ s ] = p ;

  • }

  •  

  • int cnt[ MAXN ] ;

  • double dist[ MAXN ] ;

  • bool f[ MAXN ] , flag , vis[ MAXN ] ;

  •  

  • void dfs( int v ) {

  •     f[ v ] = true ;

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

  •         if ( dist[ p -> t ] > dist[ v ] + p -> d ) {

  •             if ( ! f[ p -> t ] ) {

  •                 dist[ p -> t ] = dist[ v ] + p -> d ;

  •                 dfs( p -> t ) ;

  •             } else flag = true ;

  •             if ( flag ) break ;

  •         }

  •     }

  •     f[ v ] = false ;

  • }

  •  

  • bool check(  ) {

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

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

  •     flag = false ;

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

  •         dfs( i ) ; if ( flag ) return false ;

  •     }

  •     return true ;

  • }

  •  

  • int main(  ) {

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

  •     double l = inf , r = - inf ;

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

  •     while ( m -- ) {

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

  •         l = min( l , d ) , r = max( r , d ) ;

  •         AddEdge( s , t , d ) ;

  •     }

  •     while ( r - l > esp ) {

  •         double mid = ( l + r ) / 2.0 ;

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

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

  •                 p -> d -= mid ;

  •             }

  •         }

  •         if ( check(  ) ) l = mid ; else r = mid ;

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

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

  •                 p -> d += mid ;

  •             }

  •         }

  •     }

  •     printf( "%.8f\n" , l ) ;

  •     return 0 ;

  • }



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

历史上的今天

评论

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

页脚

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