ZJOI2007时态同步

ZJOI2007时态同步

描述

小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成,我们不妨称之为节点,并将其用数字1,2,3….进行标号。电路板的各个节点由若干不相交的导线相连接,且对于电路板的任何两个节点,都存在且仅存在一条通路(通路指连接两个元件的导线序列)。 在电路板上存在一个特殊的元件称为“激发器”。当激发器工作后,产生一个激励电流,通过导线传向每一个它所连接的节点。而中间节点接收到激励电流后,得到信息,并将该激励电流传向与它连接并且尚未接收到激励电流的节点。最终,激烈电流将到达一些“终止节点”——接收激励电流之后不再转发的节点。 激励电流在导线上的传播是需要花费时间的,对于每条边e,激励电流通过它需要的时间为te,而节点接收到激励电流后的转发可以认为是在瞬间完成的。现在这块电路板要求每一个“终止节点”同时得到激励电路——即保持时态同步。由于当前的构造并不符合时态同步的要求,故需要通过改变连接线的构造。目前小Q有一个道具,使用一次该道具,可以使得激励电流通过某条连接导线的时间增加一个单位。请问小Q最少使用多少次道具才可使得所有的“终止节点”时态同步?

输入

第一行包含一个正整数N,表示电路板中节点的个数。 第二行包含一个整数S,为该电路板的激发器的编号。 接下来N-1行,每行三个整数a , b , t。表示该条导线连接节点a与节点b,且激励电流通过这条导线需要t个单位时间。

输出

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

样例输入[复制]

3

1

1 2 1

1 3 3

样例输出[复制]

2

提示

【数据规模】 对于40%的数据,N ≤ 1000 对于100%的数据,N ≤ 500000 对于所有的数据,te ≤ 1000000

标签

zjoi2007

 
 
 
一道简单的树上dp
考虑每个点到底部用的最大时间f[x],往上更新就会有取最大值然后获取答案,就完了
代码:
 1 #include<iostream>
 2 #include<cstdio>
 3 #define N 5000005
 4 using namespace std;
 5 long long ans=0;
 6 struct node{
 7     long long u,v,w;
 8 }e[N];
 9 long long first[N],nxt[N],cnt,f[N];
10 void add(long long u,long long v,long long w){
11     e[++cnt].u=u;
12     e[cnt].v=v;
13     e[cnt].w=w;
14     nxt[cnt]=first[u];
15     first[u]=cnt;
16 }
17 void dfs(long long x,long long father){
18     long long max0=0,sum=0,tot=0;
19     for(long long i=first[x];i;i=nxt[i]){
20         long long v=e[i].v;
21         if(v==father)continue;
22         dfs(v,x);
23         max0=max(max0,f[v]+e[i].w);
24         tot++;
25         sum+=f[v]+e[i].w;
26     }
27     ans+=max0*tot-sum;
28     f[x]=max0;
29 }
30 int main(){
31     ios::sync_with_stdio(false);
32     long long n,s;
33     cin>>n>>s;
34     for(long long i=1;i<n;i++){
35         long long a,b,t;
36         cin>>a>>b>>t;
37         add(a,b,t);
38         add(b,a,t);
39     }
40     dfs(s,-1);
41     cout<<ans;
42     return 0;
43 }

 

转载于:https://www.cnblogs.com/saionjisekai/p/9669575.html

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

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

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

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

(0)


相关推荐

  • 安装试用国产系统 ——中标麒麟V7.0

    安装试用国产系统 ——中标麒麟V7.0     安装试用国产系统——中标麒麟V7.0首先自然是下载个系统的安装镜像了。下载完镜像,创建一个新的虚拟机 配置好镜像文件,开始安装了 这个倒是和一般的Linux系统没什么区别,反正中标麒麟也是基于Linux的。 加载十几秒,下面开始正式安装:  使用默认的分区就好了。  安装完成,重启一下。  然后是对系统进行简单的配置,结果忘截图了。。。。登陆进去。 中标麒麟系统的默认桌面:是不…

    2022年10月20日
  • 苹果x充电慢是什么原因_冬季冬季婴儿游泳馆水温上升慢是什么原因呢?该怎么办呢?…[通俗易懂]

    最近,天气越来越冷,正是婴儿游泳馆旺季之时,不少婴儿游泳馆经营者却反映,自己家的热水器好像不太给力了,水温上升速度很慢,已经影响了正常的经营。那么,冬季冬季婴儿游泳馆水温上升慢是什么原因呢?该怎么办呢?热水器安装位置不对空气能热水器需要安装在通风处,好安装在阳台。阳台是个半开放空间,可以自主掌握。冬季有利于新风机置换空气,夏季可以当空调使用,保证热水器的正常运行。其他热水器也要按照使用说明,选…

  • restful 幂等性(什么是幂次法则)

    理解RESTful的幂等性,并且设计符合幂等规范的高质量RESTfulAPI。怎么理解幂等性HTTP幂等方法,是指无论调用多少次都不会有不同结果的HTTP方法。不管你调用一次,还是调用一百次,一千次,结果都是相同的。还是以之前的博文的例子为例。【GET】/users#查询用户信息列表【GET】/users/1…

  • i386和i686都是什么意思呢?

    i386和i686都是什么意思呢?代表intel系列的cpu386几乎适用于所有的x86平台,不论是旧的pentum或者是新的pentum-IV与K7系列的CPU等等,都可以正常的工作!那个i指的是Intel兼容的CPU的意思,至于386不用说,就是CPU的等级啦!i586就是586等级的计算机,那是哪些呢?包括pentum第一代MMXCPU,AMD的K5,K6

  • Android2017-2018最新面试题(3-5年经验个人面试经历)

    2017-2018最新Android面试题版权声明:本文为博主原创文章,未经博主允许不得转载。原文链接:http://blog.csdn.net/huangqili1314/article/details/72792682大家好,在跟大家讲述自己的面试经历,以及遇到的面试题前,先说说几句题外话。接触Android已经3年,在工作中遇到疑难问题总是在网上(csdn大牛博客,stack…

  • Cocos2D-X2.2.3学习笔记8(处理精灵单击、双击和三连击事件)

    Cocos2D-X2.2.3学习笔记8(处理精灵单击、双击和三连击事件)

发表回复

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

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