F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 2840. -- 小强的逃跑

2840: 小强的逃跑

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 22  Solved: 9
[Submit][Status][Discuss]

Description

小强建立了一个洞穴,洞穴由N个点、M条有向边组成,可能有自环、重边。每个边有一个体力消耗值。当小强感觉
到危险的时候,它会进行低智商的逃跑行为,具体说,是从一个点开始跑,每一步:它有P的概率从这个点钻出洞
穴终止逃跑;1-P的概率沿着从当前点连出的体力消耗值最小的边移动到另一个点(此时,如果有多个连出的边的
消耗值一样且都是最小的,小强会选择到达的点的编号比较小的边。如果当前点没有连出的边,它会以相等的概率
穿越到一个随机的点,穿越不用体力,具体请见样例解释)。小强想知道,从一个点开始逃跑直到终止,它消耗的
体力的期望是多少?还有,洞穴是在动态变化的。每次,某条边的权值可能由原来的数变成另一个数。你要不停地
接受修改,同时回答小强的询问。

Input

第一行有三个数:两个正整数N,M,表示点的个数和边的个数,还有一个实数P,表示小强终止逃跑的概率。接下
来M行,每行三个正整数a,b,c,表示从点a到点b有一条权值为c的有向边。点从1编号到N。接下来一个非负整数Q,
表示操作的个数。接下来Q行,每行一个操作,是下面的格式之一:0 x y 表示把输入文件中输入的第x条边的权值
变成y1 x 表示查询当前状态下,从点x开始逃跑,小强消耗的体力的期望是多少。

Output

对于输入的每个询问操作,输出一行一个数表示小强从某个点开始逃跑的体力消耗的期望。四舍五入到整数。

Sample Input

3 3 0.1
1 2 1
1 3 1
3 1 1
4
1 1
0 1 2
1 1
1 2

Sample Output

5
9
8

HINT

【样例解释】

这张图开始的时候有3个点,3条边。

在开始状态下:

如果小强在点1,它会以0.9的概率跑向点2(消耗体力值1),0.1的概率停止;

如果小强在点2,这个点没有连出的边,所以它会以0.3的概率穿越到点1,0.3的概率穿越到点2(也就是不动),0.3的概率穿越到点3,0.1的概率停止;

如果小强在点3,它会以0.9的概率跑向点1(消耗体力值1),0.1的概率停止。   

为了计算这种情况下小强从点1出发的体力消耗期望,我们设x、y、z 分别表示小强从点1、2、3出发的体力消耗值,那么有:

x=0.9*(y+1)

y=0.3x+0.3y+0.3z

z=0.9*(x+1)

解这个方程得到x=873/187,y=783/187,z=954/187。所以,从点1 出发的体力消耗的期望是4.6684492,四舍五入之后就是5。

后来,从点1到点2的边的体力值变成了2。这样,小强从点1出发,它就会以0.9的概率跑向点3,0.1的概率停止。此时方程变成:

x=0.9*(z+1)

y=0.3x+0.3y+0.3z

z=0.9*(x+1) 

这个方程的解是x=z=9,y=54/7。所以,从点1 出发的体力消耗的期望是9,从点2出发的体力消耗的期望是7.7142857142,四舍五入之后就是8。

【数据说明】

 对于100%的数据,N<=50000,Q<=100000,1<=M<=1000000,每条边的体

力消耗值为介于1到1000的一个正整数。

数据及题解:www.lydsy.com/JudgeOnline/upload/2840.rar

Source

[Submit][Status][Discuss]

HOME Back