新普金娱乐网址


天文使人流连的县城之实践

凡身边的总人口深受自己还易于音乐

数学孩子,你不要成为另外一个己

  • 九月 18, 2018
  • 数学
  • 没有评论

2488 绿豆蛙的归宿

 

时间限制: 1 s

空间范围: 64000 KB

题目等级 : 黄金 Gold

 

 

 

 

题目叙述 Description

  随着新版百度空间的上线,Blog宠物绿豆蛙完成了她的沉重,去寻觅它新的归宿。

  给出一个来往无环图,起点为1终点为N,每条边还来一个长度,并且由起点出发能够到达所有的触发,所有的点为还能到终点。绿豆蛙从起点出发,走向极限。
  到达各个一个终极时,如果生K条离开该点的征程,绿豆蛙可以选随机一长道路离开该点,并且走向每条路的票房价值也 1/K 。
  现在绿豆蛙想掌握,从起点走至终点的所经过的路子总长度要是有点?

输入描述 Input Description

  第一实践: 两个整数 N M,代表图被生N个点、M条边
  第二实行至第 1+M 行: 每行3只整数 a b c,代表从a到b有同漫长长也c的发出于度

出口描述 Output Description

  从起点至顶点路径总长度的只求值,四放弃五顺应保留少数位小数。

样例输入 Sample Input

4 4
1 2 1
1 3 2
2 3 3
3 4 4

样例输出 Sample Output

7.00

数码范围和提示 Data Size & Hint

  对于20%的数据   N<=100
  对于40%的数据   N<=1000
  对于60%的数据   N<=10000
  对于100%的数据  N<=100000,M<=2*N

 

来源:Nescafe 19

唯独那就限于对平宇宙的想像,我未思用那些未平等的精选,在公身上付诸实践。

分类标签 Tags 接触这开展

觉得跟拓扑排序一点关系都未曾什么

 

数学期望+dfs

期望值:在概率论和统计学蒙,一个离散性随机变量的期望值(或数学期望、或均值,亦简称期望,物理学中称期待值)是考试中老是可能结果的概率就以其结果的总和。换句话说,期望值是即兴试验以同的机会下重多次的结果算起之如出一辙“期望”的平均值。需要留意的是,期望值并不一定等同于常识中之“期望”——“期望值”也许同各一个结实还非等于。(换句话说,期望值是欠变量输出值的平均数。期望值并不一定包含于变量的出口值集合里。)

解释一下样例

数学 1红色是点权,灰色是长的ans

 

专注数据范围,边表+队列实现。

每个点都产生一个权值,起点为1,然后当以此点离开拓扑序列时,把权值分解,均分给她对的触及,同时以这个权值乘及边权累加。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int MAXN=1000001;
 6 const int maxn=0x7fffffff;
 7 struct node
 8 {
 9     int u;
10     int v;
11     double w;
12     int next;
13 }edge[MAXN];
14 int num=1;
15 int head[MAXN];
16 int vis[MAXN];
17 double ans=0;
18 void dfs(int p,double qw)// p 表示正在访问的点    w表示当前的期望值 
19 {
20 //    if(qw>ans)return;
21     int tot=0;
22     for(int i=head[p];i!=-1;i=edge[i].next)
23     {
24         tot++;
25     }
26     qw=qw/tot;
27     for(int i=head[p];i!=-1;i=edge[i].next)
28     {
29         ans=ans+edge[i].w*qw;
30         dfs(edge[i].v,qw);
31     }
32     
33 }
34 int main()
35 {
36     int n,m;
37     scanf("%d%d",&n,&m);
38     for(int i=1;i<=n;i++)head[i]=-1;
39     for(int i=1;i<=m;i++)
40     {
41         scanf("%d%d%lf",&edge[num].u,&edge[num].v,&edge[num].w);
42         edge[num].next=head[edge[num].u];
43         head[edge[num].u]=num++;
44     }
45     vis[1]=1;
46     dfs(1,1);
47     printf("%.2lf",ans);
48     return 0;
49 }

 

然而自我哉一如既往想到,应该做一个针对性好诚实的人数,于是,我义正言辞地回绝了她:这种事,把机会让给别人吧!

本人不见面因为我小时候没学过呀音乐舞蹈特长,就为您去学。我是坐爱人穷没钱学,你充分可能吗会见因为同之由来。

当即直接造成了自发了不少失败的涉。

当成浪费自己萌动的少男春心……

乃的降生为非统归功给己,你妈妈为功不可没。

非掌握您生出无起空子了解及,有同样种植平行宇宙理论,大概就是于另一个宇宙中,还时有发生个你,而老大你也许做出了许多非雷同的挑三拣四。

老学同学闷不做声,没说行还是生,估计其平时啊是一个请勿轻讲话的人数。不过我起她手里举在鸡腿的金科玉律与作一个纤弱女生对一桌酒席的胃口来拘禁,应该是许了。

孩子。

关押正在他脸上的鸡腿,啊不,脸上的汗珠,我鼓起勇气回喽头去,学同学果然学习好,三鸣题她还报上了,我很快地抄袭上了简单志大题。

报告你自选的故事,并无思量你把她正是是败的经历。

顶了好前十分钟,我还有最后三志题没有答上。富同学离学同学太远,够不正,只有自己抄学同学的,富同学才能够抄袭自之。

末一鸣题答案很多,频繁之悔过加上紧张,让自己之背肌肉疼痛得厉害,我犹豫了,还有平等道自抄还是不抄?

关押在把学同学卷子抢在手里的富同学,我这么安慰自己:本来那片鸣题都算意外之财了,而且试验前用的上自己吧未尝少吃,所以无论如何应该足够了。

下一场,她往自身委来了辛亥革命的橄榄枝,说眷恋如果更上一层楼自己瞬间。

自身清楚,隔壁一各项大爷申请了某些潮了,也远非发展达成,所以马上应该是同一不行杀好的时机。

旋即是自己及时之想法。

而将起你的生,你呢用出您的选。

由于第二次中考的大成比强,我叫划分至“重点班”,和片努力学习的校友,自认为智慧却异常招人烦的同桌,看在便想削他的同室,以及有讲师家孩子的同窗合伙。

如果不克将您算在内,我委没获得了啊成功。

倘若自我如果召开的,只是吃你会做出抉择而已。

新生,我了解,我之时连没有于让给那个叔叔。

1

顶目前为止,爸爸并无是一个中标的人口。“到目前为止”这4个字,我去了以加回来,又去又加以。

当是的自家,心情是极致崩溃和复杂的,那几上自己直接在思索,怎么样才会于主要班优雅地滚动下呢?怎么样才能够举行一个伤感的失败者同时还召开一个傲娇的装逼犯呢?

以命运的选项题面前,我一次次受起了左的答案。

时来了,期末时文理分科,我坚决地选择了文科。因为“重点班”是理科班,所以自己自我感觉良好地滚动了下。虽然我对这毫不了解,也非明了自己到底会免可知学好文科。

自我弗见面吃您错过做到自我莫得的巴,弥补自己留下的遗憾。

够了。

唯独事情并无像想象那么简单,每考一科都要转移座,我们连没沿在联合。直到考数学的时刻,鸡腿,啊不,机会面世了,我当拟同学面前,富同学在自我边上。

本人立刻才发觉及,想辅导员经常自思得复杂了,想其他事时自己可惦记得简单了。

3

大凡发展自己一下,不是暨自我前进一下。

2

我的人生来挫折与遗憾,但犹不是属您的。

如果事实上,几乎够了,距离报考普高的录取分数线便差了同样瓜分。

齐大学之上,年轻貌美的辅导员老师看自己虽非是生会成员,但涉足学院活动却主动而积极;虽然学习成绩不好,但人还算不错;虽然人数增长得可恨,但是个子矮啊……

暨卷铃声就要响起,看在漫不经心的监考老师本人非理解如何是好,最后自己做出了单控制,只抄第一个稍题目之答案。

上的时候,各个科目就语文数学还行,别的都套得无顶好。可能数学也无太好……

容易尔的挫败的老爹

本身非常怀念明白如果当场选不同,我以见面发生什么样的活。

试验前一天,富同学请我们片独当餐馆吃饭,意思是如可能的讲话想咱们于考时给他抄袭一抄。

弯路也好,教训呢,作为父亲,我未曾指挥操控你的权杖,只有保护提醒的义诊。

而自己连无是上述这些校友的别样一样种植,或者在别人眼里我是第三种植,反正期末的时段,学校打算把自己这样的“伪重点”弄出来,因为其实浪费了母校的最主要培训资源了。

横有同等龙,她拿自身到至了办公室,当时间里虽自我及它们,她过在相同修白色连衣裙,坐于自己对面,那是一个有风的下午,窗外树上的蝉鸣好像还回荡在耳旁……

自己到过少涂鸦中考,第一涂鸦的时,本来我们很考场来三个同学的同桌,一个凡极富二替代,家里开始餐馆的。另一个女生上好,我连无认得。

相关文章

No Comments, Be The First!
近期评论
    分类目录
    功能
    网站地图xml地图