【BZOJ5197】Gambling Guide （最短路，期望）

题面

BZOJ权限题

洛谷

题解

假设我们求出了每个点的期望，那么对于一个点，只有向期望更小的点移动的时候才会更新答案。

即转移是：\(\displaystyle f[u]=\frac{\sum_{v,(u,v)\in E}min(f[u],f[v])+1}{d[u]}\)。

显然有\(f[n]=0\)。

那么从\(n\)开始更新其他的点，因为\(n\)是最小值，类似\(Dijkstra\)跑最短路的过程，它更新出来的值取出最小值，那么这个点不可能再被其他点所更新，即所有未确定的点中的最小值。

（似乎很不清楚啊QwQ）

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

#define MAX 300300

#define pi pair<double,int>

#define mp make_pair

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

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

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

struct Line{int v,next;}e[MAX<<1];

int h[MAX],cnt=1,dg[MAX];

inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;dg[v]+=1;}

int n,m,d[MAX];

double f[MAX],s[MAX];bool vis[MAX];

priority_queue<pi,vector<pi>,greater<pi> > Q;

int main()

{

	n=read();m=read();

	for(int i=1,u,v;i<=m;++i)u=read(),v=read(),Add(u,v),Add(v,u);

	memset(f,127,sizeof(f));f[n]=0;Q.push(mp(f[n],n));

	while(!Q.empty())

	{

		int u=Q.top().second;Q.pop();

		if(vis[u])continue;vis[u]=true;

		for(int i=h[u];i;i=e[i].next)

		{

			int v=e[i].v;if(vis[v])continue;

			d[v]+=1;s[v]+=f[u];f[v]=(s[v]+dg[v])/d[v];

			Q.push(mp(f[v],v));

		}

	}

	printf("%.10lf\n",f[1]);

	return 0;

}