hdu 4340樹形dp+染色問題

テーマ:
N個の点があって、2種類の色でマークして、それぞれの点をマークするのはすべて一定の費用を払わなければならなくて、しかもある点がマークされるならば、それに隣接する点のマークと同じ色の費用は前の2分の1になって、すべての点をマークするのに必要な最小の費用を求めます.
入力:
第1行入力N
2行目1色目のタグを入力各点のコストA[i]
2行目2色目のタグを入力各点のコストB[i]
次は隣接する都市i,jのペアです.
出力:
出力フラグの最小化費
Sample input:
3
1 2 5
3 8 1
1 2
1 3
Sample output:
3
テーマ分析:
最適解問題は,一般に動的計画の解法を考慮することができる.
ダイナミックプランニングの問題で最も重要なのは状態を確定することです.この問題は、最小の費用を求めることです.費用に関連する状態は、現在の点が染める色と、それに隣接する点が染める色、そしてそれに隣接する色が染めるかどうかです.
dp配列をこのように定義することができます.
Dp[vertrix][2][2]:
1次元は現在の点を記録する記号です.
2 D目は、現在の点のカラーを記録します.
3 Dでは、現在の点が染色される前に、現在の点の染色開始点がサブツリーにあるかどうかを記録します.
このように,隣接を探すためdpは線形ではないので,深さ優先探索により1本の探索ツリーを作り,ツリー構造に変換して動的に計画することができる.
dpの初期状態、すなわち葉ノードを決定し、葉ノードについて、葉ノードは、自身が染色の起点であってもよいし、2つでない場合でもよい.
for ( int i = 0 ; i < 2 ; i++ )
            dp[u][i][0] = cost[u][i]/2 , dp[u][i][1] = cost[u][i];
私たちは2つの色を設定して、この色の染色の起点の費用は元の費用で、染色の起点の費用は元の費用の半分ではありません.遡及すると、各色について同じ処理を行います.
 int sum = 0 , dif = INF;
        int cst = cost[u][i];
        for ( int j = 0 ; j < e[u].size() ; j++ )
        {
            int v = e[u][j];
            if ( v == fa ) continue;
            int temp = min ( dp[v][i][0] , dp[v][i^1][1] );
            sum += temp;
            dif = min ( dif , dp[v][i][1] - temp );
        }
        dp[u][i][0] = cst/2 + sum;
        dp[u][i][1] = min ( cst + sum , cst/2 + sum + dif );
    }
逐次分解分析:
まず,現在のノードをuとし,その子ノードを集合V中のvとする.
したがって、dp[u][色][0]については、現在のノードがルートであるサブツリーにおいて、その点がその色に染まっていない染色起点の最小費用であり、その色の染色起点がないため、そのサブツリールートノードも必ず染色起点ではないので、その点での染色費用は必ず半減し、しかも最適を保つために、移行の費用が固定されているため、この状態に移行する可能性のある最良の選択に違いない.この状態に移行できるようにするには、現在の点の息子がその息子のノードで同じ色に染まるか、その子の木にも染色の起点が存在しないという前提条件を満たす必要がある.異なる色の染色起点がサブツリーにあるか(染色起点がサブツリーになく、父親の色が異なる場合、その点の染色に起点は存在せず、矛盾!)の場合、それぞれの子供が2つのケースで最適なものを取り、移転費用を加えることで、dp[u][色][0]の最適なケースを得ることができます.
dp[u][色][1]では、現在のノードがその色に染まり、そのノードがルートノードであるサブツリーに染色起点がある場合、そのサブケースに移行することができる.
一、彼自身が染色の起点であり、それは息子が満足しなければならない状況であり、染色の起点を含まない状況と同じように、移転費が元の費用になっただけである.
二、第二の状況は、彼自身が染色の起点ではなく、その息子の中で息子を選び、その息子の子木の中に染色の起点が存在し、最良を保証するために、この場合、この息子のdp[v][色][1]と上記の2つの場合との差が最小(差が最小であることが保証されるため、この子木を染色起点を含む子木に変更することは、全体の費用の増加に最小限の影響を及ぼす)、
コード:

#include <cstring>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#define MAX 107
#define INF 0xfffffff

using namespace std;

vector<int> e[MAX];
int dp[MAX][2][2];
//   i          ，    j ，       ，         
int cost[MAX][2];

void dfs (  int u , int fa )
{
    if ( e[u].size() == 1 && fa != -1 )
    {
        for ( int i = 0 ; i < 2 ; i++ )
            dp[u][i][0] = cost[u][i]/2 , dp[u][i][1] = cost[u][i];
    //                       
        return ;
    }
    for ( int i = 0 ; i < e[u].size( ) ; i++ )
    {
        int v = e[u][i];
        if ( v == fa ) continue;
        dfs ( v , u );
    }
    for ( int i = 0 ; i < 2 ; i++ )
    {
        int sum = 0 , dif = INF;
        int cst = cost[u][i];
        for ( int j = 0 ; j < e[u].size() ; j++ )
        {
            int v = e[u][j];
            if ( v == fa ) continue;
            int temp = min ( dp[v][i][0] , dp[v][i^1][1] );
            //                           
            sum += temp;
            dif = min ( dif , dp[v][i][1] - temp );
            //                
        }
        dp[u][i][0] = cst/2 + sum;
        dp[u][i][1] = min ( cst + sum , cst/2 + sum + dif );
        //                 
    }
}

int n;

int main ( )
{
    int a ,b;
    while ( ~scanf ( "%d" , &n ) )
    {
        for ( int i = 0 ; i <= n ; i++ ) e[i].clear ();
        memset ( dp , 0x3f , sizeof ( dp ));
        for ( int i = 0 ; i < 2 ; i++ )
            for ( int j = 1 ; j <= n ; j++ )
                scanf ( "%d" , &cost[j][i] );
        for ( int i = 1 ; i < n ; i++ )
        {
            scanf ( "%d%d" , &a , &b );
            e[a].push_back (b) , e[b].push_back (a);
        }
        dfs ( 1 , -1 );
        //          ，                  
        printf ( "%d
" , min ( dp[1][0][1] , dp[1][1][1] ) );
    }
}