图上进行概率DP
先BFSn次算出每个点的最优前进点
然后对于每种情况DFS算期望
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
const int N=1005;
int n,m,en,h[N],deg[N],Cat,Mouse,D[N][N],P[N][N];
double f[N][N];
queue<int> Q;
struct Edge{
int b,next;
}e[N*2];
void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
deg[sa]++;
}
void BFS(int S){
Q.push(S);
D[S][S]=0;
while(!Q.empty()){
int u=Q.front(),tmp=P[S][u];
Q.pop();
for(int i=h[u];i;i=e[i].next){
int v=e[i].b;
if(D[S][v]==-1 || (D[S][u]+1==D[S][v] && tmp<P[S][v])){
D[S][v]=D[S][u]+1;
if(!tmp)P[S][v]=v;
else P[S][v]=tmp;
Q.push(v);
}
}
}
}
double DP(int Cat,int Mouse){
if(f[Cat][Mouse])return f[Cat][Mouse];
if(Cat==Mouse)return f[Cat][Mouse]=0;
if(P[Cat][Mouse]==Mouse || P[P[Cat][Mouse]][Mouse]==Mouse)return f[Cat][Mouse]=1;
double Sum=DP(P[P[Cat][Mouse]][Mouse],Mouse);
for(int i=h[Mouse];i;i=e[i].next)Sum+=DP(P[P[Cat][Mouse]][Mouse],e[i].b);
return f[Cat][Mouse]=Sum/(deg[Mouse]+1)+1;
}
int main(){
freopen("1415.in","r",stdin);
freopen("1415.out","w",stdout);
memset(D,-1,sizeof(D));
scanf("%d %d %d %d",&n,&m,&Cat,&Mouse);
for(int i=1;i<=m;i++){
int sa,sb;
scanf("%d %d",&sa,&sb);
AddEdge(sa,sb);
AddEdge(sb,sa);
}
for(int i=1;i<=n;i++)BFS(i);
printf("%.3lf\n",DP(Cat,Mouse));
return 0;
}
评论 (0)
