题目链接
大致思路
期望题的话,比较容易看出可以用记搜解决。由于每次走的时候要考虑一个距离问题,所以可以预处理出来dis[i][j]表示任意两点间的距离。因为数据范围比较小而且边权均为1,所以可以直接用bfs解决(暴力档弗洛伊德写挂导致少了40分,真实自闭了)。
这里是每次直接考虑走两步,如果走第一步的时候已经到达就返回1,否则就继续往下走第二步。
#include<bits/stdc++.h>
#define M 1005
#define db double
using namespace std;
bool cur1;
int pr[M<<1],to[M<<1],la[M],n,m,tot,S,T,sz[M];
void add(int x,int y) {
to[++tot]=y,pr[tot]=la[x],la[x]=tot;
}
int dis[M][M];
db dp[M][M];
bool mark[M][M];
db dfs(int x,int y) {
if(x==y)return 0;//已经到达了同一个点,可以直接返回
if(mark[x][y])return dp[x][y];//记搜
mark[x][y]=1;
int Mi=1e9,pos=n+1;
for(int i=la[x]; i; i=pr[i]) {
int Y=to[i];
if(dis[Y][y]<Mi||dis[Y][y]==Mi&&Y<pos)pos=Y,Mi=dis[Y][y];//找到下一步走的点,注意相同的时候找标号较小的点
}
if(pos==y)return dp[x][y]=1.0;
db res=1.0;
if(pos!=y) {
int now=pos;
Mi=1e9,pos=n+1;
for(int i=la[now]; i; i=pr[i]) {
int Y=to[i];
if(dis[Y][y]<Mi||dis[Y][y]==Mi&&Y<pos)pos=Y,Mi=dis[Y][y];
}
if(pos==y)return dp[x][y]=1.0;
db k=1.0/(sz[y]+1);//选每个点的概率
for(int i=la[y]; i; i=pr[i]) {
int z=to[i];
res+=dfs(pos,z)*k;
}
res+=dfs(pos,y)*k;
}
return dp[x][y]=res;
}
bool cur2;
struct P2 {
queue<int>Q;
bool vis[M];
void bfs(int s,int *Dis) {
while(!Q.empty())Q.pop();
Q.push(s);
memset(vis,0,sizeof(vis));
Dis[s]=0,vis[s]=1;
while(!Q.empty()) {
int x=Q.front();
Q.pop();
for(int i=la[x]; i; i=pr[i]) {
int y=to[i];
if(vis[y])continue;
Dis[y]=Dis[x]+1;
vis[y]=1,Q.push(y);
}
}
}
void solve() {
for(int i=1; i<=n; i++)bfs(i,dis[i]);
memset(mark,0,sizeof(mark));
printf("%.3f\n",dfs(S,T));
}
} p2;
int main() {
// printf("%lf\n",(&cur2-&cur1)/1024.0/1024);
freopen("cchkk.in","r",stdin);
freopen("cchkk.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&S,&T);
for(int i=1; i<=m; i++) {
int x,y;
scanf("%d%d",&x,&y);
sz[x]++,sz[y]++;
add(x,y),add(y,x);
}
p2.solve();
return 0;
}