题目：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 ;
}
网友评论