小c的岛屿 题解
简单题还能写挂,感觉没救了啊 /fd /fd /fd
由于保证每个点至少有一个出边,所以操作次数等于走的边数+1.
由于这个步数可能到达 $\infty$,对于这种问题算期望的一种方法是:对于所有还没有停止的情况,算它们的概率的和.
所以考虑一个暴力的 dp:设 $f_{i,j,k}$ 表示当前走了 $i$ 步(注意这里的步是指尝试加入了几次边,而不是走过的边数,最后答案减一即可),已经加入了 $j$ 条边,现在在点 $k$ 的概率.如果能预处理出 $h_i$ 表示 $n$ 个点 $i$ 条边的非连通图在所有 $i$ 条边的图中的概率,就可以用 $\sum_{i,j,k} f_{i,j,k} \ti