NOI 2012迷失游乐园

不错的一道题就是细节有点多, 难度评级有点虚.

$$
\rm down_u = \frac{\sum_{u\rightarrow v}down_v+L_{u,v}}{son_u}\\
\rm up_u = L_{u,f}+\frac{son_fdown_f-down_u-L_{f,u}+up_f}{son_f}
$$

$$
\rm f_u=\begin{cases}\frac{\rm son_udown_u+up_u}{\rm son_u+1}&,\rm exist fa and son Node\\
\rm \frac{\rm son_udown_u}{\rm son_u}&,\rm exist son Node\\
\rm up_u&,\rm exist father Node
\end{cases}
$$

基环树

整个图可以抽象成是一个大环上长了一些树.

每个节点都可以看成是一棵树, 那么一个点除了可以往它的子树方向走之外, 还可以向上走选择一个点走进它的子树.

  1. 求出唯一的一个环;
  2. 求出每棵树上每个点向子树中走的期望路径长度;
  3. 求出每个树根向环上走的期望路径长度;
  4. 求出树上每个点的向上走的期望路径长度;

此题的最大障碍在于有太多细节需要处理, 有的人这个题写60行, 有的人却写到了180行.
其实做法两句话就能说完.

Solution

部分函数借鉴题解, 细节实在太多, 说不定改了哪个小地方就错了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100005;
struct Edge{
int v, nxt; double c;
}e[N << 1];
int head[N], tot;
void AddEdge(int u, int v, int c) {
e[++tot] = (Edge) {v, head[u], (double)c}; head[u] = tot;
e[++tot] = (Edge) {u, head[v], (double)c}; head[v] = tot;
}
int fa[N];
int root, thesizeofvisit;
int loop[N], vis[N], du[N];
double down[N], res[N], g[N], up[N], temp[N];
void GetDown(int x, int fa) {
for (int i = head[x]; i; i = e[i].nxt)
if (e[i].v != fa and not loop [e[i].v])
GetDown(e[i].v, x), du[x] += 1, res[x] += down[e[i].v] + e[i].c;
if (du[x]) down[x] = res[x] / (double) du[x];
if (x != root) du[x] += 1;
}
void GetUp(int x, int fa) {
for (int i = head[x]; i; i = e[i].nxt)
if (e[i].v != fa and not loop[e[i].v]) {
double tmp = (res[x] - down[e[i].v] - e[i].c ) / max(1, du[x] - 1) + e[i].c;
res[e[i].v] += tmp, up[e[i].v] += tmp;
GetUp(e[i].v, x);
}
}
void FindLoop(int x) {
vis[x] = ++thesizeofvisit;
for (int i = head[x], j; i; i = e[i].nxt)
if (e[i].v != fa[x]) {
if (not vis[e[i].v]) fa[e[i].v] = x, FindLoop(e[i].v);
else if (vis[e[i].v] < vis[x])
for (loop[e[i].v] = 1, j = x; j != e[i].v; j = fa[j]) loop[j] = 1;
}
}
void OnLoop(int x, int fa) {
bool flag = 0; g[x] = 0;
for (int i = head[x]; i; i = e[i].nxt)
if (e[i].v != root and e[i].v != fa and loop[e[i].v])
flag = 1, OnLoop(e[i].v, x), g[x] += g[e[i].v] + e[i].c;
if (x == root) return;
int k = du[x] ? du[x] : 1;
if (not flag) g[x] = res[x] / (double)k;
else k = du[x] + 1, g[x] = (g[x] + res[x]) / (double)k;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1, x, y, z; i <= m; i += 1) {
scanf("%d%d%d", &x, &y, &z);
AddEdge(x, y, z);
}
if (m == n - 1) {
root = 1, GetDown(1, 0), GetUp(1, 0);
}
else {
FindLoop(1);
for (int i = 1; i <= n; i += 1) if (loop[i]) root = i, GetDown(i, 0);
memset(vis, false, sizeof vis);
for (int i = 1; i <= n; i += 1) if (loop[i]) root = i, OnLoop(i, 0), temp[i] = g[i];
for (int i = 1; i <= n; i += 1) if (loop[i]) { root = i, du[i] += 2, res[i] += temp[i]; }
for (int i = 1; i <= n; i += 1) if (loop[i]) root = i, GetUp(i, 0);
}
double Reslut = 0;
for (int i = 1; i <= n; i += 1) Reslut += res[i] / (double)du[i];
printf("%f\n", Reslut / (double)n);
return 0;
}

-------------本文结束感谢您的阅读-------------