标签: 概率

3 篇文章

YbtOJ #581. 「网络流」图上旅行
题目链接:YbtOJ #581 小 C 来到了 F 国,小 C 想好好地参观 F 国。F 国可以看一个有 $n$ 个点 $m$ 条边的有向无环图,小 C 刚开始站在 $1$ 号点。 假设现在小 C 站在 $x$ 号点: 点 $x$ 没有出边,结束旅游。点 $x$ 有 条出边,小 C 等概率地选一条边走过去。 小 J 是小 C 的好朋友,小 J 可以…
YbtOJ #735. 「动态树」毒瘤染色
题目链接:YbtOJ #735 对于一个无向图,若图中的每条边 至多处于一个无向环中,则称这个图为一个 毒瘤图。 小 A 有一个图 $G$,初始包含 $n$ 个点,没有边。显然它是一个毒瘤图。 接下来小 A 会进行 $q$ 次操作,每次操作给出两个正整数 $x,y$,要求判断往 $G$ 中加入 $(x,y)$ 后该图是否仍然是毒瘤图,若是则加入这条…