【BZOJ】1415 [Noi2005]聪聪和可可 期望DP+记忆化搜索

【题意】给定无向图,聪聪和可可各自位于一点,可可每单位时间随机向周围走一步或停留,聪聪每单位时间追两步(先走),问追到可可的期望时间。n<=1000。

【算法】期望DP+记忆化搜索

【题解】首先因为聪聪的步数大于可可,所以不可能出现循环,因此是DAG上的期望DP,用记忆化搜索解决。

每个点bfs预处理p[x][y]表示x走向y的第一步位置,设f[x][y]表示聪聪在x可可在y追上的期望时间。

$$f(x,y)=\sum_{z}\frac{f(g[g[i][j]]][j],z)}{out[x]+1}+1$$

其中z是y的邻点和y自身。

再判断一下一步到达,两步到达和重叠(可可随机到聪聪处)的情况即可。

复杂度O(n^2)。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=;
struct edge{int from,v;}e[maxn*];
int n,m,a,b,ins[maxn],first[maxn],d[maxn],q[],p[maxn][maxn],tot;
double f[maxn][maxn];
void insert(int u,int v)
{
tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;ins[u]++;
tot++;e[tot].v=u;e[tot].from=first[v];first[v]=tot;ins[v]++;
}
double dp(int a,int b)
{
if(f[a][b])return f[a][b];
if(a==b)return f[a][b]=;
if(p[a][b]==b||p[p[a][b]][b]==b)return f[a][b]=;
double ans=dp(p[p[a][b]][b],b);
for(int i=first[b];i;i=e[i].from)
ans+=dp(p[p[a][b]][b],e[i].v);
return f[a][b]=ans/(1.0*ins[b]+)+;
}
void bfs(int x)
{
memset(d,-,sizeof(d));
int head=,tail=;d[x]=;p[x][x]=;
for(int i=first[x];i;i=e[i].from)p[x][e[i].v]=e[i].v,d[e[i].v]=,q[tail++]=e[i].v;
while(head!=tail)
{
int y=q[head++];if(head>)head=;int num=p[x][y];
for(int i=first[y];i;i=e[i].from)
if(d[e[i].v]==-||((d[y]+==d[e[i].v])&&num<p[x][e[i].v]))
{
d[e[i].v]=d[y]+;
p[x][e[i].v]=num;
q[tail++]=e[i].v;
if(tail>)tail=;
}
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&a,&b);
for(int i=;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
insert(u,v);
}
for(int i=;i<=n;i++)bfs(i);
printf("%.3lf",dp(a,b));
return ;
}
上一篇:LeetCode 676. Implement Magic Dictionary实现一个魔法字典 (C++/Java)


下一篇:import 与 import static