自动搬运

查看原文

来自洛谷，原作者为

	Peter0701 得来失，聚了散，千万莫求全

搬运于2025-08-24 22:03:11，当前版本为作者最后更新于2019-10-28 21:42:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意

给定一张 $n$ 个点， $m$ 条边的无边权的无向图。有一人从 $1$ 号点出发，可以随机向一个和当前直接相连的点走去，花费 $1$ 的代价；也可以不动，重新随机一个点，也花费 $1$ 的代价。求到达 $n$ 点时的最小总花费。答案四舍五入保留 $6$ 位小数。

解法

根据期望 $dp$ 的一般设计方法，因为只有一个终点，且状态已知（期望花费为 $0$ ），因此考虑逆推。

自然地，设 $f_x$ 表示点 $x$ 到终点的期望花费。用 $E$ 表示边集， $deg_x$ 表示 $x$ 点的度数，则有 $f_x=\frac{ \sum \min \{ f_x,f_y \} }{deg_x}+1$ （边 $(x,y)$ 在 $E$ 内）。

那么，对于一个点 $x$ 来说，能对它的期望产生贡献的相邻的点 $y$ 必然有 $f_y<f_x$ 。

一开始不妨令所有的 $x$ 点在计算 $\min \{ f_x,f_y \}$ 时都为 $f_x$ （下文会证明确实只会出现这种情况）。

假设这样的 $y$ 点有 $cnt_x$ 个，则有 $f_x=\frac{ \sum f_y}{deg_x}+ \frac{(deg_x-cnt_x) \times f_x}{deg_x}+1=\frac{ \sum f_y}{deg_x}+(1- \frac{cnt_x}{deg_x} ) \times f_x+1$ （边 $(x,y)$ 在 $E$ 内且 $f_y<f_x$ ）。

因此，果断求出 $\sum f_y$ （边 $(x,y)$ 在 $E$ 内且 $f_y<f_x$ ），记为 $sum_x$ ，则 $f_x=\frac{sum_x}{deg_x}+(1- \frac{cnt_x}{deg_x} ) \times f_x+1$ ，化简得 $f_x= \frac{deg_x+sum_x}{cnt_x}$ 。

也就是说，只要相连的 $x,y$ 两点满足 $f_y<f_x$ ，我们就可以利用 $f_y$ 来更新 $f_x$ 的值。

是不是很像堆优化的 $dijkstra$ 的松弛操作呢？时间复杂度与堆优化的 $dijkstra$ 相同，为 $O((m+n)logn)$ 。

$trick$

$1.$ 利用 $f_y$ 来更新 $f_x$ 的值的算法正确性证明： 设更新后的 $x$ 点的 $f$ 值为 $f_x'$ ， $f_x-f_y=\Delta$ （显然 $\Delta>0$ ）。

由上文推出的式子得 $f_x= \frac{deg_x+sum_x}{cnt_x}$ ，更新后有 $f_x'= \frac{deg_x+sum_x+f_y}{cnt_x+1}$ ，两者相减并化简得 $f_x-f_x'=\frac{\Delta}{cnt_x+1}$ ，则 $f_x-f_x'=\frac{f_x-f_y}{cnt_x+1}$ ，即 $0<f_x-f_x'<f_x-f_y$ ，也即 $f_x>f_x'>f_y$ 。

因此每一次松弛操作不会使得 $f_x$ 变大，也不会使得其小于 $f_y$ 。证毕。

$2.$ 一个非常用不经典套路：对于确定的初始状态仅有极少数（大多数时候仅有一个），其余的状态与相邻的部分（大多数时候是相邻的点）有关的dp，考虑（放到图上）以最短路的方式进行转移。

细节

$1.$ 请注意堆的第一维数据类型是 $double$ 。

$2.$ 请注意本题是无向图，要双向建边、双向记度数。

$3.$ 请特别注意标记数组的使用和判断：每个点在自己更新完所有的点后就不能再被更新（因为此时已经是能达到的最小的值了）。

代码

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int ret=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0')
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		ret=(ret<<1)+(ret<<3)+ch-'0';
		ch=getchar();
	}
	return ret*f;
}
int n,m,u,v,w;
int num,head[600005],deg[300005],cnt[300005];
double f[300005],sum[300005];
bool vis[300005];
priority_queue<pair<double,int> > q;
struct edge
{
	int ver,nxt;
}e[600005];
inline void adde(int u,int v)
{
	e[++num].ver=v;
	e[num].nxt=head[u];
	head[u]=num;
}
inline void dijkstra()
{
	q.push(make_pair(0,n));
	while(!q.empty())
	{
		int x=q.top().second;
		q.pop();
		if(vis[x])
			continue;
		vis[x]=1;
		for(register int i=head[x];i;i=e[i].nxt)
		{
			int y=e[i].ver;
			if(vis[y])
				continue;
			cnt[y]++;
			sum[y]+=f[x];
			f[y]=(deg[y]+sum[y])/cnt[y];
			q.push(make_pair(-f[y],y));
		}
	}
}
int main()
{
	n=read();
	m=read();
	for(register int i=1;i<=m;i++)
	{
		u=read();
		v=read();
		adde(u,v);
		adde(v,u);
		deg[u]++;
		deg[v]++;
	}
	dijkstra();
	printf("%0.7lf\n",f[1]);
	return 0;
}