[省选模拟赛]path——期望+最短路
AubRain
2018-12-25 16:09:06
设 $f[i]$ 表示从 $i$ 走到 $n$ 的期望周数，答案就是 $f[1]$ 。
令 $du[i]$ 表示 $i$ 号点的度数，所以转移方程就是：
$$f[x]= \sum_{x->y} \frac{min(f[x],f[y])}{m}+\frac{m-du[x]}{m}*f[x] +1$$
化简一下就是:
$$f[x]=\frac{m+\sum_{x->y}min(f[x],f[y])}{du[x]}$$
然后我们的决策是只选择那些更优的 $f[y]$ ，即如果 $f[y]<f[x]$ 我们才用来更新 $f[x]$ 。然后那些不优秀的 $y$ 我们就当那些边不存在就行了。所以
$$f[x]=\frac{m+\sum_{x->y}f[y]}{du'[x]}$$
然后这就像最短路了~~（其实不像）~~。
用堆优化的 $dij$ ，然后每次选取 $f$ 值最小的节点去更新其它节点，这样就可以保证当前节点的 $f$ 值一定比被更新的节点的 $f$ 值更优秀。然后再更新的时候动态记录每个点的度数（被更新的次数）就行了。
**然后尝试证明一下：**
设
$$f[y]=\frac{m+f[a_1]+f[a_2]..+f[a_k]}{k}$$
那么 $f[y]$ 被 $f[x]$ 更新之后，就变成了
$$f'[y]=\frac{m+f[a_1]+f[a_2]..+f[a_k]+f[x]}{k+1}$$
我们只需要证明当 $f[x]<f[y]$ 时，$f'[y]<f[y]$ 即可。
~~显然。~~
证毕。
其实不看 $m$ 的话，$f[x]$ 相当于取了个平均数。有了 $m$ 也类似。所以就相当于 $f[x]$ 和 $f[y]$ 取了加权平均数得到了 $f'[y]$，自然有 $f[x]<f'[y]<f[y]$。
```cpp
#include<bits/stdc++.h>
#define N 100005
#define pr pair<double,int>
using namespace std;
inline void rd(int &x){
x=0;char ch=0;int w=0;
while(!isdigit(ch)) ch=getchar(),w|=ch=='-';
while( isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=w?-x:x;
}
int n,m;
double f[N],sum[N];
priority_queue<pr> q;
int head[N],cnt,v[N],d[N];
struct nd{int nxt,to;}e[N<<1];
#define For(x) for(int y,i=head[x];(y=e[i].to);i=e[i].nxt)
inline void add(int x,int y){
e[++cnt]=(nd){head[x],y};head[x]=cnt;
e[++cnt]=(nd){head[y],x};head[y]=cnt;
}
void DJ(){
while(q.size()){
int x=q.top().second;q.pop();
if(v[x]) continue; v[x]=1;
For(x) if(!v[y]){
d[y]++;sum[y]+=f[x];f[y]=(sum[y]+m)/d[y];
q.push(pr(-f[y],y));
}
}
}
signed main(){
rd(n);rd(m);
for(int x,y,i=1;i<=m;i++)
rd(x),rd(y),add(x,y);
q.push(pr(0,n));DJ();
printf("%.10lf",f[1]);
}
```