roxmax177 于 2021-06-05 18:11:58 发布原题链接
题意分析：
城市的排水系统是一个n个节点的DAG(有向无环)图，有m个污水接收口且每个污水接收口有1吨的水，放水过程中会平均分给子节点，没有子节点的水管就是最终排水口,最后按编号顺序输出每个最终排水点的污水(以分数形式)。
思路：
考虑到图是稀疏图( 0 ≤ d i ≤ 5 0 le d_i le 5 0≤di≤5)，以邻接表存图，然后以拓扑排序模拟污水流动，模拟过程中我们以一个n大小的数组，存当前每一个顶点所对应的污水量(以分数形式存储)，污水流动的计算其实就是两个分数相加，先算分母a与c的最小公倍数gbs=a*c/gcd(a,c),再根据以下公式将分数相加:
b a + d c = b ∗ g b s / a + d ∗ g b s / c g b s frac{b}{a} + frac{d}{c}=frac{b*gbs/a+d*gbs/c}{gbs} ab+cd=gbsb∗gbs/a+d∗gbs/c
然而这道题的分母,根据题意(水在从一个接收口流向一个最终排水口的过程中，不会经过超过 10 个中间排水结点),故而分母在计算过程中最坏情况下会达到 3 10 ∗ 4 10 ∗ 5 10 3^{10}*4^{10}*5^{10} 3
