HBC17709[NOI2012]迷失游乐园题解

想要检验自己的编程水平？来试试全网最全C++题库，让您在挑战中不断进步。

小Z把游乐园的抽象地图画下来带回了家，可是忘了标哪个点是大门，他只好假设每个景点都可能是大门，同时，他每次在选择下一个景点时会等概率地随机选择一个还没去过的相邻景点。

放假了，小Z觉得呆在家里特别无聊，于是决定一个人去游乐园玩。进入游乐园后，小Z看了看游乐园的地图，发现可以将游乐园抽象成有n个景点、m条道路的无向连通图，且该图中至多有一个环（即m只可能等于n或者n-1）。小Z现在所在的大门也正好是一个景点。小Z不知道什么好玩，于是他决定，从当前位置出发，每次随机去一个和当前景点有道路相连的景点，并且同一个景点不去两次（包括起始景点）。贪玩的小Z会一直游玩，直到当前景点的相邻景点都已经访问过为止。小Z所有经过的景点按顺序构成一条非重复路径，他想知道这条路径的期望长度是多少？小Z把游乐园的抽象地图画下来带回了家，可是忘了标哪个点是大门，他只好假设每个景点都可能是大门（即每个景点作为起始点的概率是一样的）。同时，他每次在选择下一个景点时会等概率地随机选择一个还没去过的相邻景点。

标签： HBC17709[NOI2012]迷失游乐园题解