首页 > 其他 > 详细

[NOI2005]聪聪与可可(期望dp)

时间:2018-09-20 15:37:21      阅读:137      评论:0      收藏:0      [点我收藏+]

题意:给一张无向图,有一只猫和一只老鼠,猫每秒会向老鼠的方向移动两个单位,若它们的距离为一,那么只会移动一个单位,老鼠会等概率向周围移动一步或不动,求猫抓到老鼠的期望时间。

Solution
luoguAC第800题。

注意到猫的运动之和猫的位置和老鼠的位置有关,我们可以对其进行预处理,注意若有多种方案的情况会向编号小的点移动。

然后发现猫和老鼠的距离一定是会减小的,不如记录状态进行记忆化搜索,这样转移是不会出现环的。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define N 1002
using namespace std;
queue<int>q;
const double eps=1e-10;
int head[N],dis[N][N],tot,tag[N][N],n,m,s,t;
bool vis[N];
double dp[N][N];
struct zzh{
    int n,to;
}e[N<<1];
inline void add(int u,int v){
    e[++tot].n=head[u];
    e[tot].to=v;
    head[u]=tot;
}
double dfs(int s,int t){
    if(dp[s][t]>eps)return dp[s][t];
    if(s==t)return 0;
    int ss=tag[s][t];
    if(ss==t)return 1;
    ss=tag[ss][t];
    if(ss==t)return 1;
    double sum=0,ans=0;
    for(int i=head[t];i;i=e[i].n)ans+=dfs(ss,e[i].to),sum++;
    ans+=dfs(ss,t);ans=ans/(sum+1)+1;
    return dp[s][t]=ans;
}
int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);int u,v;
    for(int i=1;i<=m;++i){scanf("%d%d",&u,&v);add(u,v);add(v,u);}    
    memset(dis,0x3f,sizeof(dis));memset(tag,0x3f,sizeof(tag));
    for(int i=1;i<=n;++i){
        dis[i][i]=0;
        q.push(i);
        while(!q.empty()){
            int u=q.front();q.pop();vis[u]=0;
            for(int j=head[u];j;j=e[j].n){
                int v=e[j].to;
                if(dis[i][v]>dis[i][u]+1){
                    dis[i][v]=dis[i][u]+1;
                    if(!vis[v]){
                        vis[v]=1;
                        q.push(v);
                    }
                }
            }
        }
    }
    for(int i=1;i<=n;++i)
      for(int k=1;k<=n;++k)
        for(int j=head[i];j;j=e[j].n)
          if(dis[i][k]==dis[i][e[j].to]+dis[e[j].to][k])tag[i][k]=min(e[j].to,tag[i][k]);
    printf("%.3lf",dfs(s,t));
    return 0;
}

 

[NOI2005]聪聪与可可(期望dp)

原文:https://www.cnblogs.com/ZH-comld/p/9680865.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!