bzoj1415&洛谷P4206 [NOI2005]聪聪与可可

概率与期望

题意：
每个时间单位，可可都会选择去相邻的景点(可能有多个)中的一个或停留在原景点不动。
而去这些地方所发生的概率是相等的。
当聪聪在景点 C 时，她会选一个更靠近可可的景点，如果这样的景点有多个，她会选一个标号最小的景点。
聪聪可以走一步或两步
在每个时间单位，假设聪聪先走，可可后走。若聪聪和可可位于同一个景点，则可可就被吃掉了。
细节：
猫可以走一步或两步；
老鼠可以不动；
猫必须走到离老鼠最近的点，如距离有相同，则选编号最小的点。

分析：
聪聪的移动位置是由可可的位置决定的

#include<bits/stdc++.h>
using namespace std;
#define N 1005
int to[N<<1],nex[N<<1],head[N],vis[N],dis[N][N],nx[N][N],tot=0,viss[N][N];
double dp[N][N],du[N];
void add(int a,int b)
{
    to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
queue<int >q;
void spfa(int s)
{
    memset(vis,0,sizeof(vis));
    q.push(s); dis[s][s]=0;
    while(!q.empty()){
        int u=q.front(); q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];i;i=nex[i]){
            int v=to[i];
            if(dis[s][u]+1<dis[s][v]){
                dis[s][v]=dis[s][u]+1;
                if(!vis[v]) q.push(v);
            }
        }
    }
}
double dpp(int u,int v)
{
    //printf("%d %d
",u,v);
    if(viss[u][v]) return dp[u][v];
    if(u==v) return 0;
    int step1=nx[u][v];
    int step2=nx[step1][v];
    if(step1==v||step2==v) return 1;
    double k=du[v]+1;
    for(int i=head[v];i;i=nex[i]){
        int vv=to[i];
        dp[u][v]+=(dpp(step2,vv)+1.0)/k;
        //printf("%lf
",dp[u][v]);
    }
    dp[u][v]+=(dpp(step2,v)+1.0)/k*1.0;
    viss[u][v]=1;
    return dp[u][v];
}
int main()
{
    int n,m,s,t,a,b;
    scanf("%d%d",&n,&m);
    scanf("%d%d",&s,&t);
    for(int i=1;i<=m;i++)
    scanf("%d%d",&a,&b),add(a,b),add(b,a),du[a]+=1.0,du[b]+=1.0;
    memset(dis,0x7f7f7f,sizeof(dis));
    memset(nx,0x7f7f7f,sizeof(nx));
    for(int i=1;i<=n;i++)
    spfa(i);
    for(int i=1;i<=n;i++)
     for(int j=head[i];j;j=nex[j]){
         int v=to[j];
         for(int k=1;k<=n;k++)
         if(dis[i][k]==dis[v][k]+1) nx[i][k]=min(nx[i][k],v);
    }
    /*for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
        printf("%d ",nx[i][j]);
        printf("
");
    }*/
    printf("%.3lf
",dpp(s,t));
}

要想统计答案就必须要先计算出聪聪在i位置可可在j位置聪聪下一步的移动方案
先用spfa对每一个点跑最短路再统计聪聪下一个点应该走什么
然后用记忆化搜索如果走到了return 0 或者差一两步走到return 1
否则就由大家都向前走的dp值推过来（猫肯定优选走两步）
由于猫走的路线已经定了枚举鼠走哪一个点概率就是鼠原来所在的点的出度+1（可以停留）

bzoj1415&洛谷P4206 [NOI2005]聪聪与可可

相关推荐