[省选模拟赛]path——期望+最短路

· · 个人记录

设 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]。

#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]);
}