题目描述:
- bz
- https://www.luogu.org/problemnew/show/P2081
题解:
树形 $dp$+ 基环树上树形 $dp$.
考虑 $n-1=m$ 即形成一棵树时怎么做.
设 $d[x]$ 表示 $x$ 的度数,$ch[x]$ 表示 $x$ 的儿子数.
$dn[x]$ 表示 $x$ 向下走的期望长度 (在环上指向树的方向走),$up[x]$ 表示 $x$ 向上走的期望长度 (在环上指向环上的相邻点走).
$f$ 表示 $x$ 在树上的父亲.
在树上有这几个递推式:
- $$dn[x]=\frac{
- \sum_{
- (x,v)
- }dn[v]+w(x,v)
- }{
- ch[i]
- }$$
- $$up[x]=w(f,x)+\frac{
- dn[f]*ch[f]-w(f,x)-dn[x]+up[f]*(f!=rt)
- }{
- d[f]-1
- }$$
- $$ans=\frac{
- \sum_{
- i=1
- }^{
- n
- }{
- \frac{
- dn[i]*ch[i]+up[i]*(i!=rt)
- }{
- d[f]-1
- }
- }
- }{
- n
- }$$
注意分母等于 $0$ 的情况.
树形 $dp$ 即可.
考虑把这个东西搬到基环树上.
我们可以把环拎起来, 这个东西就变成几棵树的根用环上的几条边连起来.
先用上面那个式子把 $dn$ 求出来,
然后考虑如何把 $up$ 搞出来.
显然一个环上的点在环上走只能有两个方向, 那么就可以分方向讨论一下.
由于环上最多 $20$ 个点, 我们可以枚举.
把环上的点的 $up$ 搞出来就可以树形 $dp$ 了.
注意要把上面的式子 $(f!=rt)$ 去掉.
最后统计一下就行了.
代码:
- #include <cstdio> #include <cstring> #include <algorithm> using namespace std;
- const int N = 100050;
- const double eps = 1e-7;
- template <typename T> inline void read(T & x) {
- T f = 1,
- c = 0;
- char ch = getchar();
- while (ch <'0' || ch> '9') {
- if (ch == '-') f = -1;
- ch = getchar();
- }
- while (ch>= '0' && ch <= '9') {
- c = c * 10 + ch - '0';
- ch = getchar();
- }
- x = f * c;
- }
- int n,
- m,
- hed[N],
- cnt = 1;
- struct EG {
- int to,
- nxt,
- w;
- }
- e[2 * N];
- void ae(int f, int t, int w) {
- e[++cnt].to = t;
- e[cnt].nxt = hed[f];
- e[cnt].w = w;
- hed[f] = cnt;
- }
- double up[N],
- dn[N],
- d[N],
- ch[N];
- int sta[N],
- ste[N],
- rt,
- tl;
- bool vis[N],
- cir[N];
- double dfs1(int u, int f) {
- for (int j = hed[u]; j; j = e[j].nxt) {
- int to = e[j].to;
- if (to == f || cir[to]) continue;
- dn[u] += dfs1(to, u) + e[j].w;
- }
- if (ch[u]> eps) dn[u] /= ch[u];
- return dn[u];
- }
- void dfs2(int u, int f) {
- for (int j = hed[u]; j; j = e[j].nxt) {
- int to = e[j].to;
- if (to == f || cir[to]) continue;
- up[to] = e[j].w;
- if (d[u] - 1.0> eps) up[to] += (dn[u] * ch[u] - e[j].w - dn[to] + up[u] * (d[u] - ch[u])) / (d[u] - 1.0);
- dfs2(to, u);
- }
- }
- int dfss(int u, int pre) {
- if (vis[u]) {
- rt = u;
- return 1;
- }
- vis[u] = 1;
- for (int now, j = hed[u]; j; j = e[j].nxt) {
- int to = e[j].to;
- if (j == pre) continue;
- if ((now = dfss(to, j ^ 1))) {
- if (now == 1) {
- sta[++tl] = u;
- ste[tl] = e[j].w;
- cir[u] = 1;
- if (u != rt) return 1;
- }
- return 2;
- }
- }
- return 0;
- }
- int lf(int i) {
- if (i != 1) return i - 1;
- return tl;
- }
- int rg(int i) {
- if (i != tl) return i + 1;
- return 1;
- }
- int main() {
- // freopen("tt.in","r",stdin);
- read(n),
- read(m);
- for (int f, t, w, i = 1; i <= m; i++) {
- read(f),
- read(t),
- read(w);
- ae(f, t, w),
- ae(t, f, w);
- d[f] += 1,
- d[t] += 1;
- }
- if (n> m) {
- ch[1] = d[1];
- for (int i = 2; i <= n; i++) ch[i] = d[i] - 1;
- dfs1(1, 0);
- dfs2(1, 0);
- double ans = 0.0;
- for (int i = 1; i <= n; i++) ans += (dn[i] * ch[i] + up[i] * (i != 1)) / d[i];
- ans /= n;
- printf("%.5lf\n", ans);
- return 0;
- }
- dfss(1, 0);
- for (int i = 1; i <= n; i++) ch[i] = d[i] - (cir[i] ? 2 : 1);
- for (int i = 1; i <= tl; i++) dfs1(sta[i], 0);
- for (int i = 1; i <= tl; i++) {
- double u0 = 0.0,
- now = 1.0 / 2;
- for (int j = lf(i); j != i; j = lf(j)) {
- if (j != rg(i)) u0 += now * (ste[rg(j)] + dn[sta[j]] * ch[sta[j]] / (ch[sta[j]] + 1.0));
- else u0 += now * (ste[rg(j)] + dn[sta[j]]);
- now *= 1.0 / (ch[sta[j]] + 1.0);
- }
- up[sta[i]] += u0;
- u0 = 0.0,
- now = 1.0 / 2;
- for (int j = rg(i); j != i; j = rg(j)) {
- if (j != lf(i)) u0 += now * (ste[j] + dn[sta[j]] * ch[sta[j]] / (ch[sta[j]] + 1.0));
- else u0 += now * (ste[j] + dn[sta[j]]);
- now *= 1.0 / (ch[sta[j]] + 1.0);
- }
- up[sta[i]] += u0;
- dfs2(sta[i], 0);
- }
- double ans = 0.0;
- for (int i = 1; i <= n; i++) ans += (dn[i] * ch[i] + up[i] * (d[i] - ch[i])) / d[i];
- printf("%.5lf\n", ans / n);
- return 0;
- }
- View Code