P4206[NOI2005]聪聪与可可

链接P4206 [NOI2005]聪聪与可可

• 类似于开车旅行，如果老鼠确定了那么猫的路线是确定的。
• 预处理\(g_{i,j}\)表示老鼠在\(i\)号点，猫的下一步方向，\(Bfs\)就行了
• 设\(f_{i,j}\)表示老鼠在\(i\)，猫\(j\)的期望步，转移枚举出边状态即可。
• 至于为什么这样的转移不会成环？
• 因为猫始终是顺着老鼠的方向走的，老鼠每次走一步，猫每次走两步，也就是两者距离单调不升，又因为老鼠一直在走，所以转移关系不会成环，一定是拓扑关系。

#include<bits/stdc++.h>

#define R register int

#define db double

using namespace std;

const int N=2002;

int n,m,s,t,u,v,cnt,hd[N],to[N],nt[N];

int g[N][N],vis[N],Dis[N],du[N],rec[N][N];db f[N][N];

void link(R f,R t){nt[++cnt]=hd[f],to[cnt]=t,hd[f]=cnt;}

int gi(){

    R x=0,k=1;char c=getchar();

    while(c!='-'&&(c<'0'||c>'9'))c=getchar();

    if(c=='-')k=-1,c=getchar();

    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();

    return x*k;

}

queue<int>Q;

void Bfs(R s){

	while(!Q.empty())Q.pop();

	for(R i=1;i<=n;++i)Dis[i]=1e9,vis[i]=0;

	Dis[s]=0,vis[s]=1,Q.push(s),Dis[n+1]=1e9;

	while(!Q.empty()){

		R i=Q.front();Q.pop();

		for(R k=hd[i];k;k=nt[k]){

			if(vis[to[k]])continue;

			if(Dis[to[k]]>Dis[i]+1)

				Dis[to[k]]=Dis[i]+1,Q.push(to[k]);

		}

	}

	for(R i=1;i<=n;++i)

		if(i!=s){

			g[s][i]=n+1;

			for(R k=hd[i];k;k=nt[k])

				if(Dis[to[k]]<Dis[g[s][i]]||(Dis[to[k]]==Dis[g[s][i]]&&to[k]<g[s][i]))

					g[s][i]=to[k];

		}

}

db Dfs(R s,R t){

	if(rec[s][t])return f[s][t];

	rec[s][t]=1,f[s][t]=0;

	if(s==t)return 0;

	R fir=g[s][t],sec=g[s][fir];

	if(fir==s||sec==s){f[s][t]=1;return 1;}

	for(R k=hd[s];k;k=nt[k])

		f[s][t]+=(Dfs(to[k],sec)+1)/(db)(1+du[s]);

	f[s][t]+=(Dfs(s,sec)+1)/(db)(1+du[s]);

	return f[s][t];

}

int main(){

	n=gi(),m=gi(),s=gi(),t=gi();

	for(R i=1;i<=m;++i)

		u=gi(),v=gi(),link(u,v),link(v,u),du[u]++,du[v]++;

	for(R i=1;i<=n;++i)Bfs(i);

	return printf("%.3lf\n",Dfs(t,s)),0;

}