自动搬运

查看原文

来自洛谷，原作者为

	FREEH o(≧▽≦)ツ*

搬运于2025-08-24 21:57:39，当前版本为作者最后更新于2018-08-15 19:52:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

【题目】

【解题思路】

• 分析题目，找出一些细节：
  • 猫可以走一步或两步；
  • 老鼠可以不动；
  • 猫必须走到离老鼠最近的点，如距离有相同，则选编号最小的点。
• 预处理：
  • 由于猫的走位过于神奇，无论使用什么算法都会很麻烦，因此只好进行预处理。预处理出猫在点i，老鼠在点j，猫的下一个走位$nxt[i][j]$。
  • 然而需要预处理出这个就还需要使用$SPFA$预处理出猫在点i到达所有点最短路径$dis[i][j]$，接下来才能预处理出猫的走位。
• 考虑使用概率DP，用$f[i][j]$表示猫在点i，老鼠在点j，猫抓到老鼠的期望步数是多少。
• 对于$f[i][j]$，我们进行分类讨论：
  • 如果猫和老鼠同点，即$i=j$，则$f[i][j]=0$；
  • 如果猫走一步或两步可以到达j，$f[i][j]=1$；
  • 否则$f[i][j]=sum(f[sec][k]/(p[j]+1))+1$（其中，sec表示猫走两步所到达的位置（因为走两步只算一次费用），k表示老鼠可到达的位置（含原地），p[j]表示点j的出度数（即不包含原地））。
• 这个过程可以使用记忆化搜索完成。
• 最终答案是$f[s][t]$。

【参考程序】

#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
int cur,n,m,s,t;
int head[1005],p[1005];
int dis[1005][1005],nxt[1005][1005];
bool vis[1005],visit[1005][1005];
double f[1005][1005];
struct EDGE{
	int t,next;
}e[2005];
#define INF 0x3f3f3f3f

void add(int a,int b)
{
	cur++;
	e[cur].t=b;
	e[cur].next=head[a];
	head[a]=cur;
}

queue < int > q;
void SPFA(int *dis,int *nxt,int s)
{
	dis[s]=0;
	q.push(s);
	while (!q.empty())
	{
		int u=q.front();q.pop();
		vis[u]=false;
		for (int h=head[u];h!=-1;h=e[h].next)
		{
			int v=e[h].t;
			if (dis[u]+1<dis[v])
			{
				dis[v]=dis[u]+1;
				if (!vis[v])
				{
					vis[v]=true;
					q.push(v);
				}
			}
		}
	}
}
double DFS(int u,int v)
{
	if (visit[u][v]) return f[u][v];
	if (u==v) return 0;
	int fir=nxt[u][v];
	int sec=nxt[fir][v];
	if (fir==v||sec==v) return 1;
	f[u][v]=1;
	for (int h=head[v];h!=-1;h=e[h].next)
	{
		int w=e[h].t;
		f[u][v]+=DFS(sec,w)/(p[v]+1);
	}
	f[u][v]+=DFS(sec,v)/(p[v]+1);
	visit[u][v]=true;
	return f[u][v];
}
int main()
{
	scanf("%d%d%d%d",&n,&m,&s,&t);
	memset(head,-1,sizeof head);
	for (int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
		p[a]++;p[b]++;
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
			dis[i][j]=nxt[i][j]=INF;
	}
	for (int i=1;i<=n;i++)
	{
		SPFA(dis[i],nxt[i],i);
	}
	for (int i=1;i<=n;i++)
		for (int h=head[i];h!=-1;h=e[h].next)
		{
			int t=e[h].t;
			for (int j=1;j<=n;j++)
				if (dis[i][j]-1==dis[t][j])
				{
					nxt[i][j]=min(nxt[i][j],t);
				}
		}
	/*for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
			printf("%d ", nxt[i][j]);
		printf("\n");
	}*/
	printf("%.3lf",DFS(s,t));
	return 0;
}