BZOJ 1415: [Noi2005]聪聪和可可 [DP 概率]

传送门

题意:小兔子乖乖~~~

题意·真:无向图吗,聪抓可,每个时间聪先走可后走,聪一次可以走两步,朝着里可最近且点编号最小的方向;可一次只一步,等概率走向相邻的点或不走

求聪抓住可的期望时间


和游走很像,只不过这道题限制了一个人走的方向,两人间的距离具有了阶段性!可以直接$DP$

求期望一般倒推

$f[i][j]$表示聪在$i$可在$j$抓住的期望时间

$bfs$预处理$g[i][j]$表示聪在$i$可在$j$下一步聪走到哪里

这样聪的行动就知道了,转移枚举可的行动就行啦

边界:$f[i][i]=0,\ f[i][j]=1:g[i][j]=j or g[g[i][j]][j]=j$

另一种做法:相信世界是善良的,永远输出正无穷

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} int n,m,a,b,de[N],u,v;
struct edge{
int v,ne;
}e[N<<];
int h[N],cnt;
inline void ins(int u,int v){
cnt++;
e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;
cnt++;
e[cnt].v=u;e[cnt].ne=h[v];h[v]=cnt;
} int g[N][N];
int q[N],head,tail,d[N][N];
bool inq[N];
inline void lop(int &x){if(x==N) x=;}
void bfs(int s,int *g,int *d){
head=tail=;
memset(inq,,sizeof(inq));
q[tail++]=s; d[s]=; inq[s]=;
while(head!=tail){
int u=q[head++];inq[u]=;lop(head);
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(d[v]>d[u]+ || (d[v]==d[u]+&&g[v]>g[u])){
d[v]=d[u]+;
g[v]= g[u]== ? v : g[u];
if(!inq[v]) q[tail++]=v,inq[v]=,lop(tail);
}
}
}
} double f[N][N];
double dfs(int a,int b){//printf("dfs %d %d\n",a,b);
if(a==b) return ;
if(g[a][b]==b || g[ g[a][b] ][b]==b) return ;
if(f[a][b]) return f[a][b];
double &re=f[a][b];
int t=g[ g[a][b] ][b];
re=dfs(t,b);
for(int i=h[b];i;i=e[i].ne) re+=dfs(t,e[i].v);
re=re/(de[b]+)+;
return re;
} int main(){
freopen("in","r",stdin);
n=read();m=read();a=read();b=read();
for(int i=;i<=m;i++) u=read(),v=read(),de[u]++,de[v]++,ins(u,v);
memset(d,,sizeof(d));
for(int i=;i<=n;i++) bfs(i,g[i],d[i]); //for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) printf("g %d %d %d\n",i,j,g[i][j]);
printf("%.3lf",dfs(a,b));
}
上一篇:JDK文档中关于Semaphore的正确使用以及使用场景


下一篇:CentOS 使用yum命令安装出现错误提示”could not retrieve mirrorlist http://mirrorlist.centos.org