这道题之前我写过一个巨逗比的写法(传送门:http://www.cnblogs.com/liu-runda/p/6220381.html)

当时的原因是这道题可以抽象出和”绿豆蛙的归宿”差不多的模型,而我之前写”绿豆蛙的归宿”就是用的这个巨逗比的方法.

然后前几天看了@Sengxian的博客里”绿豆蛙的归宿”的写法(传送门:https://blog.sengxian.com/algorithms/probability-and-expected-value-dynamic-programming )发现”绿豆蛙的归宿”还可以用期望的线性性写,只需要求出经过每个点的概率(也就是期望次数,因为是DAG上所以这里经过的概率和期望次数是一样的),加起来就是总共期望经过的点数,点数-1就是期望步数.感觉非常兹瓷,于是写了写这个题,顺便试了一下之前口胡的把所有状态按最短路长度排序然后DP的方法,发现过不了….无用的状态太多了会TLE.把之前那个逗比程序(求出走到每个状态的概率和从起点到这个状态的期望步数),改了改过了(不过似乎没有快多少的样子,应该是因为之前逗比代码用的dijkstra...).

#include
     
      #include
      
       #include
       
        using namespace std;const int maxn=1005;struct edge{  int to,next;}lst[maxn<<2];int len=1,first[maxn];void addedge(int a,int b){  lst[len].to=b;lst[len].next=first[a];  first[a]=len++;}double p[maxn][maxn],e[maxn][maxn];int g[maxn][maxn],dis[maxn][maxn];int n,m,s0,t0;struct node{  int v,d;  node(int _v,int _d){v=_v;d=_d;}  bool operator <(const node &B)const{    return d>B.d;  }};int vis[maxn];int T;void dijkstra(int s,int dis[]){  ++T;  priority_queue
        
          q;  q.push(node(s,0));  while(!q.empty()){    node tmp=q.top();q.pop();    if(vis[tmp.v]==T)continue;    vis[tmp.v]=T;dis[tmp.v]=tmp.d;    for(int pt=first[tmp.v];pt;pt=lst[pt].next){      if(vis[lst[pt].to]!=T)q.push(node(lst[pt].to,tmp.d+1));    }  }  int ans;  for(int i=1;i<=n;++i){     ans=i;    for(int pt=first[i];pt;pt=lst[pt].next){      if(dis[lst[pt].to]
         
          Max){        tmp=i;Max=dis[q[i][head[i]].s][q[i][head[i]].t];      }    }    Node x=q[tmp][head[tmp]++];    ans+=p[x.s][x.t];    if(x.s==x.t)continue;    int s1=g[g[x.s][x.t]][x.t];    if(s1==x.t){      p[s1][x.t]+=p[x.s][x.t];//ans+=p[x.s][x.t];      if(!used[s1][x.t]){            used[s1][x.t]=true;            if(dis[x.s][x.t]==1){                q[0][tail[0]++]=Node(s1,s1);            }else{                q[1][tail[1]++]=Node(s1,s1);            }        }    }else{      for(int pt=first[x.t];pt;pt=lst[pt].next){    p[s1][lst[pt].to]+=p[x.s][x.t]/deg[x.t];    if(!used[s1][lst[pt].to]){      used[s1][lst[pt].to]=true;      if(dis[s1][lst[pt].to]==dis[x.s][x.t]-1)q[0][tail[0]++]=Node(s1,lst[pt].to);      else if(dis[s1][lst[pt].to]==dis[x.s][x.t]-2)q[1][tail[1]++]=Node(s1,lst[pt].to);      else q[2][tail[2]++]=Node(s1,lst[pt].to);    }      }      // p[s1][x.t]+=p[x.s][x.t]/deg[x.t];      // if(q[1][tail[1]++]=Node(s1,x.t);    }      }}int main(){  scanf("%d%d",&n,&m);  scanf("%d%d",&s0,&t0);  int a,b;  for(int i=1;i<=m;++i){    scanf("%d%d",&a,&b);deg[a]++;deg[b]++;    addedge(a,b);addedge(b,a);  }  for(int i=1;i<=n;++i){    deg[i]++;addedge(i,i);    dijkstra(i,dis[i]);  }  p[s0][t0]=1.0;  q[0][tail[0]++]=Node(s0,t0);  bfs();//get possibility  printf("%.3f\n",ans-1);  return 0;}