这道题之前我写过一个巨逗比的写法(传送门: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<cstdio> #include<queue> #include<algorithm> 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<node> 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]<dis[ans])ans=lst[pt].to; if(dis[lst[pt].to]==dis[ans]&&lst[pt].to<ans)ans=lst[pt].to; } g[i][s]=ans; } } int deg[maxn]; struct Node{ int s,t; Node(int _s,int _t){s=_s;t=_t;} Node(){}; }q[3][maxn*maxn];//q[0]:-1 q[1]:-2 q[2]:-3 int head[3],tail[3]; bool used[maxn][maxn]; double ans=0; void bfs(){ while((head[0]!=tail[0])||(head[1]!=tail[1])||(head[2]!=tail[2])){ // getchar();printf("%d %d ",head[0],tail[0]); int tmp=-1,Max=-1; for(int i=0;i<3;++i){ if(head[i]!=tail[i]&&dis[q[i][head[i]].s][q[i][head[i]].t]>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 ",ans-1); return 0; }