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)


相关推荐

  • UVa 11621 – Small Factors

    UVa 11621 – Small Factors

  • C语言 — void的用法解析[通俗易懂]

    C语言 — void的用法解析[通俗易懂]C语言-void的用法解析简介​ void中文翻译为”无类型”,有的也叫”空类型”。常用在程序中对定义函数的参数类型、返回值、函数中指针类型进行声明。用法​ void应用最广泛的就是跟指针结合,即void* //无类型指针,也称为空指针,可以指向任何类型的数据 //注意一点:当我们需要使用void类型的的指针变量区指向 某一类型的变量的时候,必须要对其进行类型转换​ 这里补充一点:因为我们在定义一个指针变量的时候第一件事就是指定我们指针变量所指向的变量的类型。一

  • Nessus安裝教程[通俗易懂]

    Nessus安裝教程[通俗易懂]1、進入官網2、直接拖進kail3、拷貝此文件至root用戶下(因為安裝Nessus時需要root權限)4、使用命令dpkg-iNessus-10.1.1-debian6_amd64.deb5、啟動Nessus:/bin/systemctlstartnessusd.service6、安裝后進入官網7、註冊后郵箱得到激活密碼8、本地主機輸入連接https://kali(主機名稱):8834/9、進入頁面激活即可…

    2022年10月18日
  • 6,ORM组件XCode(撬动千万级数据)

    6,ORM组件XCode(撬动千万级数据)

  • Java程序main方法执行流程

    Java程序main方法执行流程Java程序main方法执行流程当我们编写完java源代码程序后,经过javac编译后,执行java命令执行这个程序时,是怎么一步步的调用到我们程序中的main方法的呢?今天通过查看OpenJdk的源码来揭开它的神秘面纱。java命令是在安装jre/jdk时配置到系统环境路径中去的,执行java命令时会找到bin目录下的java可执行程序,并将我们编译后的java程序类名传递进去就可以执行了。…

  • set a date for_setcallback

    set a date for_setcallbacksetTimeout只在指定时间后执行一次functionhello(){alert(“hello”);}//使用方法名字执行方法vart1=window.setTimeout(hello,1000);vart2=window.setTimeout(“hello()”,3000);//使用字符串执行方法window.clearTimeout(t1);//去掉定时器setTimeInterval//实时刷新时间单位为毫秒setInterv

发表回复

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

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