title

LUOGU 4206

analysis

根据题意我们应该对每个点进行一次 \(bfs\) 得出 \(p_{i,j}\) ，即聪聪在 \(i\) 可可在 \(j\) 时聪聪下一步的移动情况，

然后记忆化搜索，可以参考 《浅析竞赛中一类数学期望问题的解决方法》汤可因。

讲真，抄黄学长的题解跟没写一样，但是这题的状态就已经出来了：

设 \(f_{i,j}\) 表示聪聪在 \(i\) 可可在 \(j\) 时聪聪抓住可可的平均步数，\(deg[i]\) 表示点 \(i\) 的度，然后推出状态转移方程：
\[ f[i][j]=\displaystyle\frac{\displaystyle\sum_{k=1}^{deg[i]}f_{p_{p_{i,j},j},ver[i]}+f_{p_{p_{i,j},j},j}}{deg[i]+1}+1 \]

公式打得有些丑了，可以看汤爷的论文，里面也有这道题的解析，很清楚，我就溜了。

code

#include <bits/stdc++.h>

#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)

#define DeBug(x) std::cout << #x << " = " << x << std::endl

const int MaxN = 1e3 + 10;

namespace IO
{
    #define G ch = getchar()
    char buf[1<<15], *fs, *ft;
    inline char getc() { return ft == fs && (ft = (fs = buf) + fread(buf, 1, 1 << 15, stdin), ft == fs) ? 0 : *fs ++; }
    template <typename T> inline void read(T &x)
    {
        x = 0;
        T f = 1, G;
        while (!isdigit(ch) && ch ^ '-') G;
        if (ch == '-') f = -1, G;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), G;
        x *= f;
    }

    template <typename T, typename... Args>
    inline void read(T &x, Args &...args) { read(x); read(args...); }

    char Out[1<<24], *fe = Out;
    inline void flush() { fwrite(Out, 1, fe - Out, stdout); fe = Out; }
    template <typename T> inline void write(T x, char str)
    {
        if (!x) *fe++ = 48;
        if (x < 0) *fe++ = '-', x = -x;
        T num = 0, ch[20];
        while (x) ch[++ num] = x % 10 + 48, x /= 10;
        while (num) *fe++ = ch[num --];
        *fe++ = str;
    }
}

using IO::read;
using IO::write;

template <typename T> inline bool chkMin(T &a, const T &b) { return a > b ? (a = b, true) : false; }
template <typename T> inline bool chkMax(T &a, const T &b) { return a < b ? (a = b, true) : false; }
template <typename T> inline T min(T a, T b) { return a < b ? a : b; }
template <typename T> inline T max(T a, T b) { return a > b ? a : b; }

int ver[MaxN << 1], Next[MaxN << 1], head[MaxN], deg[MaxN], len;
inline void add(int x, int y)
{
    ver[++ len] = y,Next[len] = head[x], head[x] = len, ++ deg[y];
}

int dist[MaxN][MaxN], p[MaxN][MaxN];
inline void bfs(int s)
{
    memset(dist, -1, sizeof(dist));
    std::queue<int> q;
    q.push(s), dist[s][s] = 0;
    while (!q.empty())
    {
        int x = q.front(), tmp = p[s][x];
        q.pop();
        for (int i = head[x]; i; i = Next[i])
        {
            int y = ver[i];
            if (dist[s][y] == -1 || (dist[s][y] == dist[s][x] + 1 && tmp < p[s][y]))
            {
                dist[s][y] = dist[s][x] + 1;
                p[s][y] = tmp;
                if (!tmp) p[s][y] = y;
                q.push(y);
            }
        }
    }
}

double f[MaxN][MaxN];
inline double Dp(int x, int y)
{
    if (f[x][y]) return f[x][y];
    if (x == y) return 0;//聪聪已经吃掉可可
    if (p[x][y] == y || p[p[x][y]][y] == y) return f[x][y] = 1;//下一步就可以吃掉
    double tot = Dp(p[p[x][y]][y], y);
    for (int i = head[y]; i; i = Next[i]) tot += Dp(p[p[x][y]][y], ver[i]);//否则可可可能呆在原地，或有另外 d[y] 个移动方案
    return f[x][y] = tot / (deg[y] + 1) + 1;
}

int main()
{
    int n, m, C, M; read(n, m, C, M);
    for (int i = 1, x, y; i <= m; ++ i) read(x, y), add(x, y), add(y, x);
    for (int i = 1; i <= n; ++ i) bfs(i);
    printf("%.3lf\n", Dp(C, M));
    return 0;
}

BZOJ 1415: [Noi2005]聪聪和可可 概率期望Dp

原文：https://www.cnblogs.com/G-hsm/p/BZOJ1415.html