#P18454. Information Spread
Information Spread
Information Spread
Ham 先生的班级有 名学生,编号为 到 。一天,学生 得知了一条信息,随后学生们按照下述过程互相传播信息。
学生之间的关系用一张包含 个顶点、 条边的有向图表示。每条边 的权重 是 内的实数。传播过程使用两个布尔数组:aware[u] 表示学生 是否已经知道信息,visited[u] 表示其 DFS 是否已经开始过。
原题传播伪代码的完整含义如下:
SPREAD():
将 aware[1..n] 全部初始化为 False
将 visited[1..n] 全部初始化为 False
aware[1] = True
DFS(1)
DFS(u):
如果 visited[u] 为 True:
返回
visited[u] = True
按这些边在输入中出现的顺序,枚举从 u 出发的每条边 (u, v, w):
如果 aware[u] 为 True 且 aware[v] 为 False:
以概率 w 将 aware[v] 设为 True
DFS(v)
每条边都是先尝试传播,再调用 DFS(v)。DFS(v) 的调用与传播是否发生、是否成功无关。即使 已经被访问过,边上的传播条件仍须按伪代码检查;之后的 DFS 调用才因 visited[v] 返回。
请计算过程结束后,每名学生知道信息的概率,即最终 aware[i] 为 True 的概率。
输入格式
第一行包含两个整数 (,)。
接下来 行,每行包含四个整数 ,表示从 指向 的一条边,其权重为 。其中:
- ;
- ,且 。
保证没有自环;任意有序点对 至多有一条从 到 的边。保证所有顶点都能从顶点 到达,因而上述 DFS 会访问所有学生。边权可以为 ;这不会阻止 DFS 的调用。
输入只有一张图。
输出格式
输出 行,第 行包含一个整数,表示学生 最终知道信息的概率对 取模后的结果。
形式化地,若所求概率为有理数 ,则输出 ,其中 满足 。
样例 1
4 4
1 2 1 2
2 3 1 2
2 4 1 2
4 3 1 1
1
499122177
623902721
748683265
样例 2
6 12
1 2 81804 95651
2 3 39701 95895
2 4 6178 17992
3 5 72756 84510
5 6 40007 83640
2 6 60491 92219
5 3 37590 47735
4 5 6867 20289
4 3 75051 93231
6 5 48102 54448
6 1 40190 45274
1 5 37010 60312
1
947252499
124986918
535320090
929273289
551177734
样例说明
第一个样例中,学生 最开始知道信息。依次处理边 、、 和 。
学生 知道信息的概率为 。学生 知道信息的概率为 。
学生 最终仍不知道信息,有两种互斥情况:
- 学生 没有得知信息;
- 学生 已经得知信息,但处理 和 时均未成功传播。
因此,学生 最终知道信息的概率为
$$1-\frac12-\frac12\times\frac12\times\frac12=\frac38.$$