美文网首页信息学竞赛题解(IO题解)算法与数据结构数据结构
BZOJ-3232: 圈地游戏(分数规划----二分+最小割)

BZOJ-3232: 圈地游戏(分数规划----二分+最小割)

作者: AmadeusChan | 来源:发表于2019-02-28 14:20 被阅读0次

    题目: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 ;
    
    }
    

    相关文章

      网友评论

        本文标题:BZOJ-3232: 圈地游戏(分数规划----二分+最小割)

        本文链接:https://www.haomeiwen.com/subject/dbbhuqtx.html