题目:http://www.lydsy.com/JudgeOnline/problem.php?id=3232
分数规划的常用做法,二分答案,然后最小割判定,题解传送门:http://hi.baidu.com/strongoier/item/0425f0e5814e010265db0095
代码:
#include <cstdio>
#include <cstring>
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
#define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )
const double inf = 0x7fffffff , esp = 0.000001 ;
const int maxn = 55 , maxm = 21000 , maxv = 5010 ;
struct edge {
edge *next , *pair ;
int t ;
double f ;
} E[ maxm ] ;
edge *pt , *head[ maxv ] , *d[ maxv ] ;
void Init( ) {
memset( head , 0 , sizeof( head ) ) ;
pt = E ;
}
void add( int s , int t , double f ) {
edge *p = pt ++ ;
p -> t = t , p -> next = head[ s ] , p -> f = f ;
head[ s ] = p ;
}
void addedge( int s , int t , double a , double b ) {
add( s , t , a ) , add( t , s , b ) ;
head[ s ] -> pair = head[ t ] , head[ t ] -> pair = head[ s ] ;
}
int gap[ maxv ] , h[ maxv ] , S , T ;
double min( double x , double y ) {
return x < y ? x : y ;
}
double sap( int v , double flow ) {
if ( v == T ) return flow ;
double rec = 0 , ret ;
for ( edge *p = d[ v ] ; p ; p = p -> next ) if ( p -> f > esp && h[ p -> t ] + 1 == h[ v ] ) {
ret = sap( p -> t , min( flow - rec , p -> f ) ) ;
p -> f -= ret , p -> pair -> f += ret , d[ v ] = p ;
if ( ( rec += ret ) > flow - esp ) return flow ;
}
if ( ! ( -- gap[ h[ v ] ] ) ) h[ S ] = T ;
gap[ ++ h[ v ] ] ++ , d[ v ] = head[ v ] ;
return rec ;
}
double maxflow( ) {
memset( gap , 0 , sizeof( gap ) ) ;
memset( h , 0 , sizeof( h ) ) ;
for ( int i = 0 ; i ++ < T ; ) {
d[ i ] = head[ i ] ;
}
gap[ 0 ] = T ;
double flow = 0 ;
for ( ; h[ S ] < T ; flow += sap( S , inf ) ) ;
return flow ;
}
int a[ maxn ][ maxn ] , b[ maxn ][ maxn ] , c[ maxn ][ maxn ] , n , m , node[ maxn ][ maxn ] , V = 0 ;
double sum ;
bool check( double x ) {
Init( ) ;
rep( i , n ) addedge( node[ i ][ 0 ] , T , inf , 0 ) , addedge( node[ i ][ m + 1 ] , T , inf , 0 ) ;
rep( i , m ) addedge( node[ 0 ][ i ] , T , inf , 0 ) , addedge( node[ n + 1 ][ i ] , T , inf , 0 ) ;
rep( i , n ) rep( j , m ) addedge( S , node[ i ][ j ] , a[ i ][ j ] , 0 ) ;
double cost ;
REP( i , 0 , n ) rep( j , m ) {
cost = double( b[ i ][ j ] ) * x ;
addedge( node[ i ][ j ] , node[ i + 1 ][ j ] , cost , cost ) ;
}
rep( i , n ) REP( j , 0 , m ) {
cost = double( c[ i ][ j ] ) * x ;
addedge( node[ i ][ j ] , node[ i ][ j + 1 ] , cost , cost ) ;
}
return maxflow( ) < sum - esp ;
}
int main( ) {
scanf( "%d%d" , &n , &m ) ;
rep( i , n ) rep( j , m ) scanf( "%d" , &a[ i ][ j ] ) , sum += double( a[ i ][ j ] ) ;
REP( i , 0 , n ) rep( j , m ) scanf( "%d" , &b[ i ][ j ] ) ;
rep( i , n ) REP( j , 0 , m ) scanf( "%d" , &c[ i ][ j ] ) ;
REP( i , 0 , ( n + 1 ) ) REP( j , 0 , ( m + 1 ) ) {
node[ i ][ j ] = ++ V ;
}
S = ++ V ; T = ++ V ;
double l = 0 , r = inf , mid ;
check( 3 ) ;
while ( r - l > esp ) {
mid = ( l + r ) / 2.0 ;
if ( check( mid ) ) l = mid ; else r = mid ;
}
printf( "%.3f\n" , l ) ;
return 0 ;
}
网友评论