P2081 [NOI2012]迷失游乐园

NOI2012D1T3

~~想屁吃D2T3233~~另外美食节那个题就是优化时间戳做一遍更新一遍的技巧就咕掉了

给定一棵带权树/基环树，随机选一点出发走不重复路径，问期望带权路径长度.

我们还是先考虑树的部分,一个经典状态设计,

$down[i]$ 表示从i点出发向下走的期望长度,不难发现走不回来 $up[i]$ 表示从i点第一步出发向上的概率,除了第一步硬点其他步数随意,就是他父亲第二歩可以向上也可以向下

好的我们先考虑 $down[i]$ ,son[u]表示u的度数-1

down[u]=\frac{1}{son[u]}\sum_{v \subset u} {down[v]+w_{u,v}}

就是枚举每个儿子考虑走下去啊,注意概率不是son[u]+1是因为我们硬点了

再是up,需要down数组辅助才行

up[i]=w_{i,fa}+\frac{up[fa]+down[fa]*son[fa]-down[i]-w_{i,k}}{son[fa]}

这个直接理解就是父亲可以走的边有 $son[fa]$ 条,每条的期望考虑一下就是了

易知每个点的答案 $Ans_i=\frac{up[i]+down[i]*son[i]}{son[i]+1}$

再来考虑基环树吧

对于一个环上每个点up[i],我们考虑重新列式子

第一遍,硬点每个点只能第一步顺时针走求出一个概率,第二遍,硬点每个点只能向右走求出一个概率两遍求个均值

up[i]=\sum{P_j*(\frac{son[j]*down[j]}{son[j]+1}+w_{i,j})}

注意,i和j在环上是连续的, $P_j$ 表示i到环上第j个点的概率

因为环很小很小所以这个可以环^2呢

那么这个 $P_j$ 怎么求?还是环^2就行,在有之前硬点的情况下,我们从i出发dfs到i+1,则 $P_{i+1}=P_{i}*\farc{1}{(son[i]+2)}$

这样就可以了,细节实现时候我们可以把环拎出来建虚环或者用双向链表

code:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 2e5 + 10;
int home[MAXN], tag[MAXN], circle[MAXN], pre[MAXN], nex[MAXN];

double son[MAXN], fa[MAXN], up[MAXN], down[MAXN];

int n, m, ccnt, tot, flag;
double dis[25][25], ans;
bool vis[MAXN];
struct edge {
    int to, nxt;
    double w;
} e[MAXN << 1];

inline void ct(int u, int v, double w) {
    e[++ccnt].to = v;
    e[ccnt].nxt = home[u];
    e[ccnt].w = w;
    home[u] = ccnt;
}

void find_circle(int u, int F) {
    vis[u] |= 1;
    for(register int i = home[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if(v == F)continue;
        if(vis[v]) {
            flag = v;
            return ;
        }
        find_circle(v, u);
        if(flag > 0) {
            if(flag == u)flag = -1;
            return ;
        }
        if(flag == -1)break;
    }
    vis[u] = 0;
}//如果一个节点在环上则vis=1

void dfs_down(int u, int F) {
    for(register int i = home[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if(vis[v] || v == F)continue;
        fa[v] = 1;
        dfs_down(v, u);
        son[u]++;
        down[u] += down[v] + e[i].w;
    }
    if(son[u])down[u] /= son[u];
    // printf("%d %lf\n",u,down[u]);
}

void dfs_up(int u, int F, double w) {
    up[u] = w;
    if(fa[F] + son[F] > 1)up[u] += (fa[F] * up[F] + son[F] * down[F] - down[u] - w) / (fa[F] + son[F] - 1);
    //如果不大于1就说明他已经走到了叶子
    //命秒没
    for(register int i = home[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if(v != F)dfs_up(v, u, e[i].w);
    }
}

void dfs_circle(int u, int F) {
    if(tag[u])return ;//可能绕完回来了
    circle[++tot] = u;
    tag[u] = tot;
    //u是环上的第几号点
    fa[u] = 2;
    for(register int i = home[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if(!vis[v] || v == F)continue;
        pre[v] = u;
        nex[u] = v;
        //链表
        dfs_circle(v, u);
        int nw = tag[u], to = tag[v];
        dis[nw][to] = dis[to][nw] = e[i].w;
        break;
        //走一步就行
    }
}

inline void type1() {
    find_circle(1, 0);
    //puts("qwq");
    for(register int i = 1; i <= n; ++i) {
        if(vis[i]) {
            dfs_circle(i, 0);
            //把双向链表搞出来
            break;
        }
    }
    //puts("qaq");
    for(register int i = 1; i <= tot; ++i)dfs_down(circle[i], 0);
    //qwq
    for(register int i = 1; i <= tot; ++i) {
        int u = circle[i];
        double P1 = 1, P2 = 1;
        for(register int j = nex[u]; j != u; j = nex[j]) {
            int w = dis[tag[pre[j]]][tag[j]];
            if(nex[j] == u)up[u] += P1 * (w + down[j]);
            else up[u] += P1 * (w + (down[j] * son[j]) / (son[j] + 1));
            P1 /= (son[j] + 1);
        }
        for(register int j = pre[u]; j != u; j = pre[j]) {
            int w = dis[tag[nex[j]]][tag[j]];
            if(pre[j] == u)up[u] += P2 * (w + down[j]); //相邻啊
            else up[u] += P2 * (w + (down[j] * son[j]) / (son[j] + 1));
            P2 /= (son[j] + 1); //不相邻
        }
        up[u] /= 2;//顺着和逆着的概率一样
    }
    for(register int j = 1; j <= tot; ++j) {
        for(register int i = home[circle[j]]; i; i = e[i].nxt) {
            int v = e[i].to;
            if(!vis[v]) {
                dfs_up(v, circle[j], e[i].w);
            }
        }
    }
}

inline void type2() {
    dfs_down(1, 0);
    for(register int i = home[1]; i; i = e[i].nxt) {
        dfs_up(e[i].to, 1, e[i].w);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for(register int i = 1, u, v, w; i <= m; ++i) {
        scanf("%d%d%d", &u, &v, &w);
        ct(u, v, w);
        ct(v, u, w);
    }
    m == n ? type1() : type2();
    for(register int i = 1; i <= n; ++i) {
        ans += (up[i] * fa[i] + down[i] * son[i]) / (fa[i] + son[i]);
        //统计每个点作为起点权值
    }
    ans /= n;
    //乘上概率
    printf("%.5lf\n", ans);
    return 0;
}
/*
4 4
1 2 3
2 3 1
3 4 4
4 1 2
*/

夏晓光(loveJY)的博客

再来考虑基环树吧

P3823 [NOI2017]蚯蚓排队