NOI2005 聪聪和可可

Sol

记忆化搜索.

\(f[u][v]\) 表示聪聪在 \(u\) ,可可在 \(v\) ,聪聪抓到可可的期望.

预处理出 \(u\) 到 \(v\) 最短路径编号最小的点,记为 \(g[u][v]\) .

点 \(u\) 的度数记为 \(du[u]\) .

显然递归出口就是

\(u==v\) 那么此时 \(f[u][v]=0\) 已经在同一个点了,不会再互相伤害了.

\(p[u][v]=v\) 或者 \(p[p[u][v],v]=v\) 那么就互相伤害吧! \(f[u][v]=1\)

对于其他情况

\(f[u][v]=(\frac{1}{du[v]+1} \sum_{k=1}^{du[i]} f[g[g[u][v]][v],p]+f[g[g[u][v]][v],v])+1,p\in Edge(v,p)\)

Code

#include<cstdio>

#include<cstring>

#include<vector>

#include<queue>

#include<iostream>

using namespace std;

#define N 1005

inline int in(int x=0,char ch=getchar()){ while(ch>'9'||ch<'0') ch=getchar();

    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x; }

int n,m,s,t;int d[N],pre[N],p[N][N],du[N];bool b[N],vis[N][N];

double f[N][N];vector<int> g[N];

void SPFA(int S){

    queue<int> q;memset(d,0x3f,sizeof(d));memset(b,0,sizeof(b));

    d[S]=0,q.push(S),b[S]=1;

    for(int u,v;!q.empty();){

        u=q.front(),q.pop();

        for(int i=0;i<du[u];i++){

            if(d[v=g[u][i]]>d[u]+1||(d[v]==d[u]+1&&u<pre[v])){

                d[v]=d[u]+1,pre[v]=u;if(!b[v]) q.push(v),b[v]=1;

            }

        }b[u]=0;

    }for(int i=1;i<=n;i++) if(i!=S) p[i][S]=pre[i];

}

double DFS(int u,int v){

    if(u==v) return f[u][v]=0;if(p[u][v]==v) return f[u][v]=1;if(p[p[u][v]][v]==v) return f[u][v]=1;

    if(f[u][v]>1e-9) return f[u][v];f[u][v]=1;int nxt=p[p[u][v]][v];

    for(int i=0;i<du[v];i++){

        f[u][v]+=DFS(nxt,g[v][i])/(du[v]+1);

    }f[u][v]+=DFS(nxt,v)/(du[v]+1);return f[u][v];

}

int main(){

    n=in(),m=in(),s=in(),t=in();

    for(int i=1,u,v;i<=m;i++)

        du[u=in()]++,du[v=in()]++,g[u].push_back(v),g[v].push_back(u);

    for(int i=1;i<=n;i++) SPFA(i);

    return printf("%.3lf\n",DFS(s,t)),0;

}