[NOI2005]聪聪与可可

题目链接:Click here

Solution:

首先设\(f(i,j)\)表示聪聪在点\(i\)，可可在点\(j\)时的期望时间，设\(tot_x\)表示与\(x\)相邻的点的个数，\(to_i\)表示与\(i\)相邻的点集

因为可可每次可能走到与自己相邻的某个点，也可能不动，这些选择都是等概率的，则我们可以得出式子:
\[ f(i,j)=\frac{1}{tot_j+1}(1+f(now,j)+\sum_{v\in to_j}1+f(now,v))\\ f(i,j)=\frac{1}{tot_j+1}(f(now,j)+\sum_{v\in to_j}f(now,v))+1 \]
dp的过程我们可以用记忆化搜索来完成，现在我们只需要知道对于每一个\(f(i,j)\)，\(now\)是多少就行了

这个也很简单，先用spfa处理出距离，再来预处理就好了，最后我们只需要输出\(f(S,T)\)就行了

Code:

#include<bits/stdc++.h>
const int N=1e3+1;
const int inf=2147483647;
using namespace std;
int n,m,s,t,cnt,head[N],dis[N][N];
int go[N][N],apr[N][N],vis[N];
double f[N][N];
struct Edge{int nxt,to;}edge[N<<1];
void ins(int x,int y){
    edge[++cnt].nxt=head[x];
    edge[cnt].to=y;head[x]=cnt;
}
queue<int> q;
void spfa(int v0){
    for(int i=1;i<=n;i++)
        dis[v0][i]=inf;
    dis[v0][v0]=0;q.push(v0);
    memset(vis,0,sizeof(vis));
    while(!q.empty()){
        int x=q.front();q.pop();vis[x]=0;
        for(int i=head[x];i;i=edge[i].nxt){
            int y=edge[i].to;
            if(dis[v0][x]+1<dis[v0][y]){
                dis[v0][y]=dis[v0][x]+1;
                if(!vis[y]) q.push(y),vis[y]=1;
            }
        }
    }
}
double dfs(int x,int y){
    if(apr[x][y]) return f[x][y];
    apr[x][y]=1;int tot=1;
    int u1=go[x][y],u2=go[u1][y];
    if(u1==y||u2==y) return f[x][y]=1.0;
    f[x][y]=1.0;
    for(int i=head[y];i;i=edge[i].nxt) ++tot;
    for(int i=head[y];i;i=edge[i].nxt){
        int to=edge[i].to;
        f[x][y]+=1.0*1/tot*dfs(u2,to);
    }f[x][y]+=1.0/tot*dfs(u2,y);
    return f[x][y];
}
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int main(){
    n=read(),m=read(),s=read(),t=read();
    for(int i=1;i<=m;i++){
        int x=read(),y=read();
        ins(x,y),ins(y,x);
    }
    for(int i=1;i<=n;i++) spfa(i);
    for(int i=1;i<=n;i++) apr[i][i]=1,f[i][i]=0.0;
    memset(go,0x3f,sizeof(go));
    for(int i=1;i<=n;i++)   
        for(int u=head[i];u;u=edge[u].nxt){
            int y=edge[u].to;
            for(int j=1;j<=n;j++)
                if(dis[y][j]+1==dis[i][j])
                    go[i][j]=min(go[i][j],y);
        }printf("%.3lf\n",dfs(s,t));
    return 0;
}