BZOJ1415 [Noi2005]聪聪和可可

BZOJ1415 [Noi2005]聪聪和可可

首先要预处理处当前聪聪在i点，可可在j点的时候聪聪下一步要走到哪里（这我都没想出来。。。

然后就比较简单了，根据套路，这个聪聪在x节点的期望应该是可可在j节点走到各种地方后，聪聪跟上的期望，当然也要算出可可留在原地，聪聪跑两步的期望。最后一加就好了。

一开始是这么想的，可害怕转移的东西互相依赖就没继续想了。。结果发现并不会相互依赖

#include<bits/stdc++.h>
const int N = 1020;
int n,e,cnt;
int c,m,last[N];
int st[N][N],pre[N],C[N],v[N];
int dis[N][N];
double f[N][N];
struct edge {
    int to,next;
}E[N<<1];
inline int add(int x,int y){
    cnt++;E[cnt].to=y,E[cnt].next=last[x],last[x]=cnt;
    C[x]++;
}
inline int bfs(int s){
    std::queue<int> q;
    while(!q.empty()) q.pop();
    q.push(s);
    dis[s][s]=0;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=last[x];i;i=E[i].next){
            if(E[i].to==x) continue;
            if(dis[s][E[i].to]==-1||(dis[s][E[i].to]==dis[s][x]+1&&st[s][x]<st[s][E[i].to])){
                dis[s][E[i].to]=dis[s][x]+1;
                st[s][E[i].to]=st[s][x];
                if(!st[s][x])st[s][E[i].to]=E[i].to;
                q.push(E[i].to);
            }
        }
    }
}
inline double find(int s,int x){//CC在S，KK在X的期望步数 
    if(f[s][x]) return f[s][x];
    if(s==x) return 0;
    if(st[s][x]==x||st[st[s][x]][x]==x) return f[s][x]=1;
    double ans=find(st[st[s][x]][x],x); 
    for(int i=last[x];i;i=E[i].next){
        ans+=1.0*find(st[st[s][x]][x],E[i].to);
    }
    return f[s][x]=ans/(C[x]+1)+1;
}
int main (){
    scanf("%d %d",&n,&e);
    scanf("%d %d",&c,&m);
    for(int i=1;i<=e;++i){
        int x,y;
        scanf("%d %d",&x,&y);
        add(x,y),add(y,x);
    }
    memset(dis,-1,sizeof(dis));
    for(int i=1;i<=n;++i){
        bfs(i);
    }
    double ans=find(c,m);
    printf("%.3lf",ans);
    return 0;
}