首页 > 其他分享 >[ZJOI2007] 时态同步

[ZJOI2007] 时态同步

时间:2024-09-11 11:02:11浏览次数:9  
标签:时态 同步 val int 电路板 pos 激励 ZJOI2007 节点

[ZJOI2007] 时态同步

题目描述

小 Q 在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成,我们不妨称之为节点,并将其用数字 \(1,2,3\cdots\) 进行标号。电路板的各个节点由若干不相交的导线相连接,且对于电路板的任何两个节点,都存在且仅存在一条通路(通路指连接两个元件的导线序列)。

在电路板上存在一个特殊的元件称为“激发器”。当激发器工作后,产生一个激励电流,通过导线传向每一个它所连接的节点。而中间节点接收到激励电流后,得到信息,并将该激励电流传向与它连接并且尚未接收到激励电流的节点。最终,激励电流将到达一些“终止节点”――接收激励电流之后不再转发的节点。

激励电流在导线上的传播是需要花费时间的,对于每条边 \(e\),激励电流通过它需要的时间为 \(t_e\),而节点接收到激励电流后的转发可以认为是在瞬间完成的。现在这块电路板要求每一个“终止节点”同时得到激励电路――即保持时态同步。由于当前的构造并不符合时态同步的要求,故需要通过改变连接线的构造。目前小 Q 有一个道具,使用一次该道具,可以使得激励电流通过某条连接导线的时间增加一个单位。请问小 Q 最少使用多少次道具才可使得所有的“终止节点”时态同步?

输入格式

第一行包含一个正整数 \(N\),表示电路板中节点的个数。

第二行包含一个整数 \(S\),为该电路板的激发器的编号。

接下来 \(N-1\) 行,每行三个整数 \(a,b,t\)。表示该条导线连接节点 \(a\) 与节点 \(b\),且激励电流通过这条导线需要 \(t\) 个单位时间。

输出格式

仅包含一个整数 \(V\),为小 Q 最少使用的道具次数。

样例输入

3
1
1 2 1
1 3 3

样例输出

2

树形DP:

设计状态 \(dp_i\) 为以 \(i\) 为根节点下所用道具的最小次数,此状态不能直接转移。

设计辅助数组 \(val_i\) 表示 \(i\) 节点到以 \(i\) 为根节点的子树中到各个叶子节点的路径的最大值。

\(val\) 数组的转移:

$ val_i = max(val_{to_i} + to_{val} , val_i)$

\(dp\) 数组的转移:

\(dp_i = \sum dp_{to_i} + val_i - (val_{to} + to_{val})\)

其中 \(to_{val}\) 表示 \(i \to to\) 的边权

代码:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define int long long
const int MAXN = 5e5 + 7;
int n,r;
int x,y;
int dp[MAXN],val[MAXN];
struct NODE{
    int to,val;
};
vector<NODE> tree[MAXN];
void sumup(int pos,int fa){
    for(NODE to : tree[pos]){
        if(to.to != fa){
            sumup(to.to,pos);
            val[pos] = max(val[pos],val[to.to] + to.val);
        }
    }
}
void dfs(int pos,int fa){
    for(NODE to : tree[pos]){
        if(to.to != fa){
            dfs(to.to,pos);
            dp[pos] += dp[to.to] + val[pos] - (val[to.to] + to.val);
        }
    }
}
signed main(){
    scanf("%lld%lld", &n, &r);
    for(int i = 1;i < n;i++){
        int val;
        scanf("%lld%lld%lld", &x, &y, &val);
        tree[x].push_back({y,val});
        tree[y].push_back({x,val});
    }
    sumup(r,0);
    dfs(r,0);
    cout<<dp[r]<<endl;
    return 0;
}

标签:时态,同步,val,int,电路板,pos,激励,ZJOI2007,节点
From: https://www.cnblogs.com/wyl123ly/p/18407887

相关文章

  • 思源笔记-S3-七牛云-多设备同步
    文档参考:思源笔记配置S3同步、思源笔记使用七牛云编写日期:2024.9.9一、思源笔记安装思源笔记官方下载地址选择对应系统版本进行下载双击【SiYuanInstaller.exe】进行安装二、注册账号注册账号是为了购买订阅,订阅后才提供S3/WEBDAV同步功能打开SiYuan......
  • LTE PSS主同步信号PSS搜索阶段频偏估计
    频偏的影响:本期要讲到PSS搜索阶段,整数倍频偏和小数倍频偏的估计方法,整数倍频偏指的是子载波间隔的整数倍比如15k、30k等,小数倍频偏指的是一个子载波间隔以内的。在OFDM通信系统中,频偏是一个比较敏感的词,正常如果频偏估不准会带来一系列的问题,比如OFDM信号的正交性遭到破坏,带来......
  • 解决微软OneNote不能同步的问题
    https://blog.csdn.net/zhuwei/article/details/140926025前言最近发现开启本地http代理服务器后onenoteforwindows10无法同步,但是我的代理配置是无误的.经过查询发现,这个是由于微软的UWP应用的新特性引起的.在win10中的所有UWP应用均运行在被称为appcontainer的虚拟沙箱......
  • MySQL主从节点运用chrony实现时钟同步
    在数据库主从复制环境中,保持主从节点之间的时间同步是非常重要的,因为数据库的复制操作通常依赖于时间戳。如果主从节点的时钟不同步,可能会导致复制延迟或者数据不一致的情况。使用chrony来同步主从数据库节点的时钟,确保它们的时间保持一致。主节点安装chronyyuminsta......
  • 250M高速采样数字化仪、2路同步AD数据采集卡——PCIe8912M/8914M/8916M
    品牌:阿尔泰科技型号:PCIe8912M/8914M/8916M概述:PCIe8912M/8914M/8916M数据采集卡,该板卡提供250MS/s12/14/16位2通道同步采样数字化仪,专为输入信号高达100M的高频和高动态范围的信号而设计。与Labview无缝连接,提供图形化API函数。模拟输入范围可以通过软件编程设置为±1V......
  • 【开源dcluster】Seatunnel数据同步之MySQL同步到doris
    源码Gitee地址:https://gitee.com/zhenglv123456/dcluster在线文档:https://47.121.127.33:8090/在线体验:http://36.155.14.171:12345/dolphinscheduler/ui/login账号密码:test/test123 创建同步任务操作步骤:1.点击创建任务 2.配置同步脚本 3.设置同步时间......
  • cuda block之间的同步测试
    cudablock之间的同步测试一.小结二.复现过程三.输出本文测试了cudablock之间的同步行为一.小结1.cuda没有提供block之间的同步机制2.本文通过一个计数器,实现同步(while判断全局变量计数是否等于总的线程数)3.当GPU可以容纳所有的线程时A.while循环中为空,ker......
  • 数据同步方式何来“高级”与“低级”之说?场景匹配才是真理!
    导读:数据同步方式的重要性对于数据集成领域的兴从业者不言而喻,选择正确的数据同步方式能让数据同步工作的成果事半功倍。目市面上的数据同步工具很多,提供的数据同步方式也有多种,不同的数据同步方式有什么区别?如何选择适合自己业务需求的数据同步方式呢?本文将对此进行深入分析,并深......
  • 数据同步方式何来“高级”与“低级”之说?场景匹配才是真理!
    导读:数据同步方式的重要性对于数据集成领域的兴从业者不言而喻,选择正确的数据同步方式能让数据同步工作的成果事半功倍。目市面上的数据同步工具很多,提供的数据同步方式也有多种,不同的数据同步方式有什么区别?如何选择适合自己业务需求的数据同步方式呢?本文将对此进行深入分析,并......
  • 数据同步和数据备份
       日常使用的移动手机或者是电脑等其它电子产品都是每天在产生不同的数据。数据安全性的 保证需要有很多的计算机程序设计的运行程序进行有效保证。电子产品是硬件设备,硬件设 备就像机器机械一样是可以看得见摸得着的具体物件设施。物质和能量,源头物料可以通过 不同的设......