BZOJ-1040: [ZJOI2008]骑士（DP）

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