NOI2012. 迷失游乐园
放假了，小Z觉得呆在家里特别无聊，于是决定一个人去游乐园玩
进入游乐园后，小Z看了看游乐园的地图，发现可以将游乐园抽象成有 $n$ 个景点、$m$ 条道路的无向连通图，且该图中至多有一个环（即 $m$ 只可能等于 $n$ 或者 $n-1$，并且环上节点个数不超过 $25$ 个）。小Z现在所在的大门也正好是一个景点
小Z不知道什么好玩，于是他决定，从当前位置出发，每次随机去一个和当前景点有道路相连的景点，并且同一个景点不去两次（包括起始景点）。贪玩的小Z会一直游玩，直到当前景点的相邻景点都已经访问过为止。小Z所有经过的景点按顺序构成一条非重复路径，他想知道这条路径的期望长度是多少？
小Z把游乐园的抽象地图画下来带回了家，可是忘了标哪个点是大门，他只好假设每个景点都可能是大门（即每个景点作为起始点的概率是一样的）
同时，他每次在选择下一个景点时会等概率地随机选择一个还没去过的相邻景点
这题是 NOI2012 的一道题目，前几天突然想找一题环套树的来做一做于是就找到了这题
首先来考虑一下树的情况 假设最后求得的期望长度是 $E$，从点 $u$ 出发的期望长度是 $E(u)$，因为从哪个点出发是等概率的，所以 $E = \frac{1}{N}\sum_{u \in V} E(u)$
因为这是一棵树，并且不能走已经走过的节点，那么一旦开始往下走，就一定会是一直往下走到底，我们可以用 $E_d(u)$ 来表示从节点 $u$ 出发，第一步是往下走的期望长度，那么 \[ E_d(u) = \frac{1}{|son(u)|}\sum_{v \in son(u)} \left(E_d(v) + w(u, v)\right) \]
这里 $son(u)$ 表示 $u$ 的儿子的集合，特别的，当 $|son(u)|=0$ 的时候，$E_d(u) = 0$
除了向下走以外，还有可能向上走，一直走到根或者从某个点开始向下，那么，我们用 $E_u(u)$ 来表示从节点 $u$ 开始，第一步是向上走的期望长度，然后，从 $u$ 走到它的父亲 $f$ 之后，有两种选择，继续向上，或者向下，所以 \[ E_u(u) = \frac{E_u(f) + \sum_{v \in son(f), v \neq u} \left(E_d(v) + w(f, v)\right)}{|son(u)|} + w(f, u) \]
当 $f$ 是根节点时，没有办法再向上走，所以 \[ E_u(u) = \frac{\sum_{v \in son(f), v \neq u} \left(E_d(v) + w(f, v)\right)}{|son(u)| - 1} + w(f, u) \]
当 $f$ 是根结点，并且只有一个儿子的时候 \[ E_u(u) = w(f, u) \]
然后最后从节点 $u$ 出发的期望就是（特别的，$E(root) = E_d(root)$） \[ E(u) = \frac{|son(u)|\cdot E_d(u) + E_u(u)}{|son(u)| + 1} \]
到这里树的情况的答案就出来了。然后变成环套树之后，我们可以先进行拓扑排序，然后对于每棵树求出 $E_d$，求的方法和上面一样
接着来求环上节点（也就是每棵树的根）的 $E_u$，对于从 $u$ 出发，在环上可以从两个方向走，走到某一个节点 $v$ 时，可以选择往下走（这时候用 $E_d(v)$），或者继续在环上走，算出走到 $v$ 的概率，然后乘上去就可以算出环上的 $E_u$
求出了环上的 $E_u$ 之后，每棵树上的 $E_u$ 也和前面的情况基本相同（具体可以看代码）
#include <cstdio>
#include <cstring>
const int MaxN = 100001, MaxE = 200001;
int total;
int N, M;
int head[MaxN], point[MaxE], weight[MaxE], next[MaxE];
double up[MaxN], down[MaxN];
int deg[MaxN], que[MaxN], deg2[MaxN];
int circle[MaxN], circle_num;
void add_edge(int u, int v, int w)
{
weight[++total] = w;
point[total] = v;
next[total] = head[u];
head[u] = total;
++deg[u];
}
void tree_down(int u, int fa)
{
int son = 0;
for(int k = head[u]; k; k = next[k])
{
int v = point[k];
if(v == fa) continue;
tree_down(v, u);
down[u] += weight[k] + down[v];
++son;
}
if(son) down[u] /= son;
else down[u] = 0.0;
}
void tree_up(int u, int fa)
{
int son = 0;
double sum = 0.0;
for(int k = head[u]; k; k = next[k])
{
int v = point[k];
if(v == fa) continue;
sum += weight[k] + down[v];
++son;
}
if(fa)
{
++son;
sum += up[u];
} else if(son == 1) {
++son;
}
for(int k = head[u]; k; k = next[k])
{
int v = point[k];
if(v == fa) continue;
up[v] = (sum - down[v] - weight[k]) / (son - 1.0) + weight[k];
tree_up(v, u);
}
}
void circle_down(int u, int fa)
{
int son = 0;
for(int k = head[u]; k; k = next[k])
{
int v = point[k];
if(v == fa || deg[v]) continue;
circle_down(v, u);
down[u] += weight[k] + down[v];
++son;
}
if(son) down[u] /= son;
else down[u] = 0.0;
}
void circle_up(int u, int fa)
{
int son = 0;
double sum = 0.0;
for(int k = head[u]; k; k = next[k])
{
int v = point[k];
if(v == fa || deg[v])
continue;
sum += weight[k] + down[v];
++son;
}
if(!fa)
{
son += 2;
sum += up[u] * 2.0;
} else {
++son;
sum += up[u];
}
for(int k = head[u]; k; k = next[k])
{
int v = point[k];
if(v == fa || deg[v])
continue;
up[v] = (sum - weight[k] - down[v]) / (son - 1.0) + weight[k];
circle_up(v, u);
}
}
void solve_circle(int u)
{
double sum = 0.0;
for(int k = head[u]; k; k = next[k])
{
if(!deg[point[k]]) continue;
double p = 0.5, len = weight[k];
int nxt = point[k], from = u;
while(nxt)
{
if(deg2[nxt] > 2)
{
sum += (down[nxt] + len) * p
* (deg2[nxt] - 2.0) / (deg2[nxt] - 1.0);
p /= deg2[nxt] - 1.0;
}
int temp = 0;
for(int t = head[nxt]; t; t = next[t])
{
int v = point[t];
if(!deg[v] || v == from || v == u)
continue;
temp = v;
len += weight[t];
break;
}
from = nxt;
nxt = temp;
}
if(deg2[from] == 2)
{
sum += len * p;
} else {
sum += (len + down[from]) * p;
}
}
up[u] = sum;
}
void topology_sort()
{
int qhead = 0, qtail = 0;
for(int i = 1; i <= N; ++i)
{
if(deg[i] == 1)
{
que[qtail++] = i;
deg[i] = 0;
}
}
while(qhead != qtail)
{
int u = que[qhead++];
for(int k = head[u]; k; k = next[k])
{
int v = point[k];
if(!deg[v])
continue;
if(--deg[v] == 1)
{
que[qtail++] = v;
deg[v] = 0;
}
}
}
}
void find_circle()
{
int first = 1;
for(; first <= N; ++first)
{
if(deg[first])
break;
}
circle_num = 1;
circle[0] = first;
int u = first;
do {
int next_v = 0, pre = 0;
if(circle_num >= 2) pre = circle[circle_num - 2];
for(int k = head[u]; k; k = next[k])
{
int v = point[k];
if(v == pre || !deg[v])
continue;
next_v = v;
break;
}
if(next_v == 0)
{
for(int k = head[u]; k; k = next[k])
{
int v = point[k];
if(!deg[v]) continue;
next_v = v;
break;
}
}
u = circle[circle_num++] = next_v;
} while(u != first);
--circle_num;
}
int main()
{
std::scanf("%d %d", &N, &M);
for(int i = 0; i != M; ++i)
{
int u, v, w;
std::scanf("%d %d %d", &u, &v, &w);
add_edge(u, v, w);
add_edge(v, u, w);
}
if(N == M + 1)
{
tree_down(1, 0);
tree_up(1, 0);
double ans = down[1];
for(int u = 2; u <= N; ++u)
ans += (up[u] + down[u] * (deg[u] - 1.0)) / deg[u];
std::printf("%lf", ans / N);
} else {
std::memcpy(deg2, deg, sizeof(deg));
topology_sort();
find_circle();
for(int i = 0; i != circle_num; ++i)
{
circle_down(circle[i], 0);
deg[circle[i]] = deg2[circle[i]];
}
for(int i = 0; i != circle_num; ++i)
solve_circle(circle[i]);
for(int i = 0; i != circle_num; ++i)
circle_up(circle[i], 0);
double ans = 0.0;
for(int u = 1; u <= N; ++u)
{
int w = deg[u] ? 2 : 1;
ans += (up[u] * w + down[u] * (deg2[u] - w)) / deg2[u];
}
std::printf("%lf", ans / N);
}
return 0;
}