[NOI2005]聪聪与可可 题解 期望

· · 题解

题目传送门

题意

Sol

期望类题目。

首先看这个 n \le 1000 发现（大概）可以 n^3。

那么我们不妨先暴力跑出 p_{i,j} 代表 \text{A} 在 i，\text{B} 在 j 时 \text{A} 下次应该走到的位置。

可以用 \texttt{Dijkstra} 求出任意两点之间最短路，然后枚举两点及边暴力跑出 p_{i,j}。

由于边数小，离 n^3 还很远，完全能跑过。（

我们以 t_i 表示 i 点的度数，w_i 表示与 i 相邻的点集，f_{i,j} 表示 \text{A} 在 i，\text{B} 在 j 的期望步数。

可得对于 \forall i f_{i,i}=0。

同时若 p_{i,j}==j 或 p_{p_{i,j},j}==j f_{i,j}=1。

分析每次暴力往下跑后，可得通项 f_{i,j}=1+\dfrac{\sum\limits_{k=1}^{t_k}f_{p_{p_{i,j},j},w_{j,k}}+f_{p_{p_{i,j},j},j}}{t_i+1}。

显然可以记忆化搜索。

于是便能完成问题。

/*
***
还要继续努力
成为一名烤咕学家哦
***
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e3+5;
const double eps=1e-5;
ll n,e,c,m,p[N][N],dis[N][N];
double f[N][N];
vector<ll> w[N];
template <typename T> void rd(T &x){
    ll fl=1;x=0;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') fl=-fl;
    for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
    x*=fl;
}
void wr(ll x){
    if(x<0) x=-x,putchar('-');
    if(x<10) putchar(x+'0');
    if(x>9) wr(x/10),putchar(x%10+'0');
}
double dp(ll u,ll v){
    if(u==v) return f[u][v]=0.0;
    if(p[u][v]==v||p[p[u][v]][v]==v) return f[u][v]=1.0;
    if(f[u][v]!=0.0) return f[u][v];
    for(ll k=0;k<w[v].size();k++) f[u][v]+=dp(p[p[u][v]][v],w[v][k]);f[u][v]+=dp(p[p[u][v]][v],v);
    f[u][v]/=(double)(w[v].size()+1);f[u][v]+=1.0;
    return f[u][v];
}
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    rd(n);rd(e);rd(c);rd(m);
    for(ll i=0,u,v;i<e;i++) rd(u),rd(v),w[u].push_back(v),w[v].push_back(u);
    memset(dis,-1,sizeof(dis));
    for(ll i=1;i<=n;i++){
        queue<ll> q;q.push(i);dis[i][i]=0;
        while(!q.empty()){
            ll u=q.front();q.pop();
            for(ll j=0;j<w[u].size();j++)
                if(dis[i][w[u][j]]==-1) dis[i][w[u][j]]=dis[i][u]+1,q.push(w[u][j]);
        }
    }
    memset(p,0x3f,sizeof(p));
    for(ll i=1;i<=n;i++)
        for(ll k=0;k<w[i].size();k++)
            for(ll j=1;j<=n;j++)
                if(dis[i][j]==dis[w[i][k]][j]+1) p[i][j]=min(p[i][j],w[i][k]);
    cout<<fixed<<setprecision(3)<<dp(c,m);puts("");
    return 0;
}