URAL 1018 Binary Apple Tree

URAL 1018 Binary Apple Tree

    可以用f[i][j]表示递推到第i个节点时保留j个树枝的最优解,决策的时候要么只从某个子树中选取,要么就同时从两个子树中选取,而且如果选择了某个子树中的树枝,那么就必须选择和这个子树相连接的树枝。

#include<stdio.h>
#include<string.h>
#define MAXD 110
#define MAXM 210
int N, Q, e, first[MAXD], next[MAXM], v[MAXM], w[MAXM], f[MAXD][MAXD];
void add(int x, int y, int z)
{
    v[e] = y, w[e] = z;
    next[e] = first[x], first[x] = e ++;
}
void init()
{
    int i, j, k, x, y, z;
    memset(first, -1, sizeof(first));
    e = 0;
    for(i = 1; i < N; i ++)
    {
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);    
    }
}
void dfs(int cur, int fa)
{
    int i, j, n = 0, g[2], num[2];
    for(i = first[cur]; i != -1; i = next[i])
        if(v[i] != fa)
        {
            g[n] = v[i], num[n] = w[i];
            ++ n;
            dfs(v[i], cur);
        }
    if(n == 1)
    {
        for(i = 1; i <= Q; i ++)
            f[cur][i] = f[g[0]][i - 1] + num[0];    
    }
    else if(n == 2)
    {
        f[cur][1] = num[0] > num[1] ? num[0] : num[1];
        for(i = 2; i <= Q; i ++)
        {
            for(j = 0; j < 2; j ++)
                if(f[g[j]][i - 1] + num[j] > f[cur][i])
                    f[cur][i] = f[g[j]][i - 1] + num[j];    
            for(j = 0; j <= i - 2; j ++)
                if(f[g[0]][j] + num[0] + f[g[1]][i - 2 - j] + num[1] > f[cur][i])
                    f[cur][i] = f[g[0]][j] + num[0] + f[g[1]][i - 2 - j] + num[1];
        }
    }
}
void solve()
{
    memset(f, 0, sizeof(f));
    dfs(1, -1);
    printf("%d\n", f[1][Q]);    
}
int main()
{
    while(scanf("%d%d", &N, &Q) == 2)
    {
        init();    
        solve();
    }
    return 0;    
}

 

 

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/110415.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • siamfc++代码_c语言代码怎么理解

    siamfc++代码_c语言代码怎么理解文章目录前言一、论文翻译二、论文代码1.backbone网络前言记录自己阅读复现SiamFC的全过程,包括论文翻译,代码理解等一、论文翻译论文原文:链接:https://pan.baidu.com/s/1wvXra0Ji6L9IMVZikaUs9Q提取码:s7t3本文是Siam系列跟踪论文的开篇之作,兼容了速度与精度,引起跟踪社区极大的关注。论文中对一些细节描述分非常充分,适合精读本文。二、论文代码代码参考;https://github.com/HonglinChu/SiamTra.

  • ubuntu20.04安装opencv_ubuntu opencv安装

    ubuntu20.04安装opencv_ubuntu opencv安装更新源 sudo apt update 安装相关包 sudo apt-get install build-essential cmake git libgtk2.0-dev pkg-config libavcodec-dev libavformat-dev libswscale-dev libjasper 报错:无法定位到 libj…

  • traceroute详解[通俗易懂]

    traceroute详解[通俗易懂]traceroute详解1.traceroute基本概念traceroute(Windows系统下是tracert)命令利用ICMP协议定位您的计算机和目标计算机之间的所有路由器。TTL值可以反映数据包经过的路由器或网关的数量,通过操纵独立ICMP呼叫报文的TTL值和观察该报文被抛弃的返回信息,traceroute命令能够遍历到数据包传输路径上的所有路由器。traceroute是一条缓慢…

  • IO流的分类_io流的作用

    IO流的分类_io流的作用IO流的分类可以分为以下三种:第一种:输入流和输出流按照流的流向来分,可以分为输入流和输出流。输入,输出都是从程序运行所在内存的角度来划分的。输入流:只能从中读取数据,而不能向其写入数据,由InputStream和Reader作为基类。输出流:只能向其写入数据,而不能从中读取数据。由OutputStream和Writer作为基类第二种:字节流和字符流字节流和字符流的用法几乎完全一样,区…

    2022年10月20日
  • windows默认颜色设置_微信怎么设置颜色皮肤

    windows默认颜色设置_微信怎么设置颜色皮肤emwin使用了默认皮肤之后就不能够容易的重新设置颜色。这边我提供一种解决的方法,以button为例子。正常设置皮肤BUTTON_SetDefaultSkin(BUTTON_SKIN_FLEX);后效果如下:此时设置颜色并没有效果。换成如下代码,/*************************定制皮肤*****************************/   BUTTON_…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号