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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1040: [ZJOI2008]骑士(DP)  

2014-02-14 13:41:00|  分类: oi,bzoj,DP |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


这个图就是一堆环,每个环上面可能挂着一些树,那么就DP就可以了。


代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
 
using namespace std ;
 
#define MAXN 1000100
#define ll long long 
 
const ll inf = ( ll )( 0x7fffffff ) * ( ll )( 0x7fffffff ) ;
 
struct edge {
    edge *next ;
    int t ;
} *head[ MAXN ] ;
 
void AddEdge( int s , int t ) {
    edge *p = new( edge ) ;
    p -> t = t , p -> next = head[ s ] ;
    head[ s ] = p ;
}
 
int n , num[ MAXN ] ;
ll w[ MAXN ] , value[ MAXN ][ 2 ] ;
stack < int > S ;
 
void Tree_dp(  ) {
    memset( value , 0 , sizeof( value ) ) ;
    while ( ! S.empty(  ) ) S.pop(  ) ;
    for ( int i = 0 ; i ++ < n ; ) value[ i ][ 1 ] = w[ i ] ;
    for ( int i = 0 ; i ++ < n ; ) if ( ! num[ i ] ) S.push( i ) ;
    while ( ! S.empty(  ) ) {
        int v = S.top(  ) ; S.pop(  ) ;
        for ( edge *p = head[ v ] ; p ; p = p -> next ) {
            if ( ! ( -- num[ p -> t ] ) ) S.push( p -> t ) ;
            value[ p -> t ][ 0 ] += max( value[ v ][ 0 ] , value[ v ][ 1 ] ) ;
            value[ p -> t ][ 1 ] += value[ v ][ 0 ] ;
        }
    }
}
 
ll ans = 0 , dp[ MAXN ][ 2 ] ;
bool f[ MAXN ] ;
 
int b[ MAXN ] , bn = 0 ;
 
void dfs( int v ) {
    f[ v ] = false , b[ ++ bn ] = v ;
    if ( f[ head[ v ] -> t ] ) dfs( head[ v ] -> t ) ;
}
 
void Ring_dp(  ) {
    for ( int i = 0 ; i ++ < n ; ) f[ i ] = num[ i ] > 0 ;
    memset( dp , 0 , sizeof( dp ) ) ;
    for ( int i = 0 ; i ++ < n ; ) {
        dp[ i ][ 0 ] = value[ i ][ 0 ] , dp[ i ][ 1 ] = value[ i ][ 1 ] ;
    }
    for ( int i = 0 ; i ++ < n ; ) if ( f[ i ] ) {
        ll ret ;
        bn = 0 ;
        dfs( i ) ;
        dp[ i ][ 1 ] = 0 ;
        for ( int j = 1 ; j < bn ; ++ j ) {
            dp[ b[ j + 1 ] ][ 0 ] += max( dp[ b[ j ] ][ 0 ] , dp[ b[ j ] ][ 1 ] ) ;
            dp[ b[ j + 1 ] ][ 1 ] += dp[ b[ j ] ][ 0 ] ;
        }
        ret = max( dp[ b[ bn ] ][ 0 ] , dp[ b[ bn ] ][ 1 ] ) ;
        for ( int j = 0 ; j ++ < bn ; ) {
            dp[ b[ j ] ][ 0 ] = value[ b[ j ] ][ 0 ] ;
            dp[ b[ j ] ][ 1 ] = value[ b[ j ] ][ 1 ] ;
        }
        for ( int j = 1 ; j < bn ; ++ j ) {
            dp[ b[ j + 1 ] ][ 0 ] += max( dp[ b[ j ] ][ 0 ] , dp[ b[ j ] ][ 1 ] ) ;
            dp[ b[ j + 1 ] ][ 1 ] += dp[ b[ j ] ][ 0 ] ;
        }
        ret = max( ret , dp[ b[ bn ] ][ 0 ] ) ;
        ans += ret ;
    }
}
 
int main(  ) {
    memset( head , 0 , sizeof( head ) ) ;
    memset( num , 0 , sizeof( num ) ) ;
    scanf( "%d" , &n ) ;
    for ( int i = 0 ; i ++ < n ; ) {
        int t ; scanf( "%lld%d" , w + i , &t ) ;
        AddEdge( i , t ) , ++ num[ t ] ;
    }
    Tree_dp(  ) ;
    Ring_dp(  ) ;
    printf( "%lld\n" , ans ) ;
    return 0 ;
}


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

历史上的今天

评论

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

页脚

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