ural 1018 Binary Apple Tree(樹形dp|経典)

2288 ワード

ダイナミック？プログラム ACM-ICC征途

本論は http://blog.csdn.net/shuangde800
---------------------------------------
テーマリンク: url-1018
題意
一本の辺に権利のある二叉の木をあげて、ノード番号は1～nで、1はルートノードです.いくつか辺を切り落として、ただq条の辺だけを保留することを求めて、このq条の辺の構成の子樹ルートノードの要求は1です.このツリーの最大権利はいくらですか?
考え方
非常に古典的な木の形dpの問題は、私が今やった問題によって、いくつかの道がこの問題から生まれたのです. f(i,j)は、サブツリーiを表し、j個のノード(注:ノード)の最大の重みを保持する.各辺の権利は、接続された2つのノードのうちの息子ノードの権利値と見なされる. それなら、すべてのiのサブツリーをグループ化してリュックサックを作ることができます.すなわち、各サブツリーは1、2、…j−1の辺を選んで、それに割り当てられます. 状態が以下に移動します f(i,j)=max｛max｛f(i,j-k)＋f(v,k)|1<=k ans=f(1,q+1)
コード

/**=====================================================
 *   This is a solution for ACM/ICPC problem
 *
 *   @source      : ural-1018 Binary Apple Tree
 *   @description :   dp
 *   @author      : shuangde
 *   @blog        : blog.csdn.net/shuangde800
 *   @email       : [email protected]
 *   Copyright (C) 2013/09/01 18:43 All rights reserved. 
 *======================================================*/
#include 
#include 
#include 
#include 
#include 
#define MP make_pair
using namespace std;

typedef pairPII;
typedef long long int64;
const int INF = 0x3f3f3f3f;

const int MAXN = 110;
vectoradj[MAXN];
int n, q;
int tot[MAXN]; 
int f[MAXN][MAXN];

int dfs(int u, int fa) {
    tot[u] = 1;
    for (int e = 0; e < adj[u].size(); ++e) {
        int v = adj[u][e].first;
        if (v == fa) continue;
        tot[u] += dfs(v, u);
    }

    for (int e = 0; e < adj[u].size(); ++e) {
        int v = adj[u][e].first;
        int w = adj[u][e].second;
        if (v == fa) continue;
        for (int i = tot[u]; i > 0; --i) {
            for (int j = 1; j < i && j <= tot[v]; ++j) {
                f[u][i] = max(f[u][i], f[u][i-j] + f[v][j] + w); 
            } 
        }
    }
    return tot[u];
}

int main(){

    while (~scanf("%d%d", &n, &q)) {

        for (int i = 0; i <= n; ++i)
            adj[i].clear();

        for (int i = 0; i < n - 1; ++i) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            adj[u].push_back(MP(v, w));
            adj[v].push_back(MP(u, w));
        }
        memset(f, 0, sizeof(f));
        dfs(1, -1);
        printf("%d
", f[1][q+1]);
    }
    return 0;
}

JavaScriptの中のいくつかの常用方法