bzoj 1415 聪聪和可可 【期望】

可以先预处理出当聪聪在 i 点，可可在 j 点时，聪聪下一步到达的点的编号，记为p[i,j]，bfs即可。

设f[i,j]表示聪聪在 i，可可在 j 时的期望步数，w[i,j]为与i相邻的第 j 个点编号，t[i]为 i 点的度数，则有

f[i,j]=∑t[i]k=1f[p[p[i,j],j],w[j,k]]+f[p[p[i,j],j],j]t[i]+1

然后记忆化搜索。

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#define INF 1000000000
#define N 1005
#define D double
using namespace std;

int n,m,siz,s,t;
int first[N],next[N*],to[N*];
int p[N],d[N],map[N][N],trans[N][N];
D f[N][N];

void inser(int x,int y)
{
    next[++siz]=first[x];
    first[x]=siz;
    to[siz]=y;
}

void bfs(int S)
{
    int head=,tail=;
    map[p[]=S][S]=;
    map[][S]=INF;
    while (head^tail)
    {
        int x=p[++head];
        for (int i=first[x];i;i=next[i])
            if (map[S][to[i]]==-)
                map[S][p[++tail]=to[i]]=map[S][x]+;
    }
}

void init()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for (int x,y,i=;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        inser(x,y),inser(y,x);
        d[x]++,d[y]++;
    }
    memset(map,-,sizeof(map));
    for (int i=;i<=n;i++) bfs(i);
    for (int i=;i<=n;i++)
        for (int j=;j<=n;j++) if (i^j)
            for (int y,k=first[i];k;k=next[k])
                if (map[trans[i][j]][j]>map[y=to[k]][j]||map[trans[i][j]][j]==map[y][j]&&y<trans[i][j])
                    trans[i][j]=y;
}

D work(int x,int y)
{
    if (f[x][y]!=) return f[x][y];
    if (x==y) return ;
    if (map[x][y]<=) return f[x][y]=;
    D ret=;
    for (int i=first[y];i;i=next[i])
        ret+=work(trans[trans[x][y]][y],to[i]);
    ret+=work(trans[trans[x][y]][y],y);
    return f[x][y]=ret/(d[y]+)+;
}

int main()
{
    init();
    printf("%.3f",work(s,t));

    return ;
}