Poj Solution 2486

http://poj.org/problem?id=2486

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
int value[100];
int gone[100][201],m,K,n;
int back[100][201];
list<int> e[100];
void merge_back(int bk1[], int bk2[], int bk[], int maxstep )
{
    int i,j;
    for( i=0; i<=maxstep; i++ )
    {
        bk[i] = bk2[i];
        for( j=2; j<=i; j++ )
        if( bk1[j-2] + bk2[i-j] > bk[i] )
            bk[i] = bk1[j-2] + bk2[i-j];
    }
    
    return ;    
}    
void merge_gone(int go1[], int bk1[], int go2[], int bk2[], int go[], int maxstep )
{
    int i,j;
    for( i=0; i<=maxstep; i++ )
    {
        go[i] = go2[i];

        for( j=1; j<=i; j++ )
        if( go1[j-1] + bk2[i-j] > go[i] )
            go[i] = go1[j-1] + bk2[i-j];
        
        for( j=2; j<=i; j++ )
        if( bk1[j-2] + go2[i-j] > go[i] )
            go[i] = bk1[j-2] + go2[i-j];
    }

    return ;
}
int back_temp[201],gone_temp[201];
void calculate(int root,int maxstep,int father)
{
    int i,j;    
    list<int>::iterator iter;
    if( root>100 || root<0 )
        int *p = new int[10000000];    
    for( i=0; i<=maxstep ; i++ )
    {
        gone[root][i] = back[root][i] = value[root];
    }
    if( maxstep == 0 ) return ;
    for( iter = e[root].begin(); iter != e[root].end() ; iter++ )
    if( *iter != father )
    {
        calculate( *iter, maxstep-1 , root );
        merge_back( back[*iter], back[root], back_temp, maxstep );
        merge_gone( gone[*iter], back[*iter], gone[root], back[root], gone_temp,maxstep );
                    
        copy( back_temp, back_temp+maxstep+1, back[root] );
        copy( gone_temp, gone_temp+maxstep+1, gone[root] );
    }

}
bool init()
{
    int i, a, b;
    cin>>n>>K;
    if( n>100 || K>200 )
        while(cout<<"faint");
    if( cin.fail() )return false;
    
    if( K > 2*n ) K = 2*n;    

    for( i=0; i<n; i++ )
    {
        cin >> value[i];
        e[i].clear();
    }    
    for( i=0; i<n-1; i++ )
    {
        cin >> a >> b;
        e[a-1].push_back( b-1 );
        e[b-1].push_back( a-1 );
    }    

    return true;
}
void doit()
{
    int answer = 0;    
    calculate( 0, K, -1);     
    cout << gone[0][K] << endl;
}
int main()
{
    while( init() )
    {
        doit();
    }
    return 0;
}



											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *