一个点到达终点的期望步数 \(E_i=\sum_{(i,j)\in G}\frac{E_j+1}{out[i]}\)，\(out[i]\)为点\(i\)的出度。

那么对于一个DAG可以直接在反向图上拓扑+DP求解。

于是对于环内高斯消元，缩点后拓扑+DP。

无解(无限步)的情况: 起点到不了终点；起点能够走到一个环，且在这个环内无法走到终点(走不出去)。

ps:1.T连出的边不能计算。

2.期望的计算式有个+1！

3.建反向边！

4.重边

---

注：

如果\(E_i\)表示从起点到点\(i\)的期望步数，那么起点可能多次到达点\(i\)，\(E_i\)这个值就。。（可以就直接拿起点做例子？）

如果\(E_i\)表示到达终点的期望步数就没有这个问题。

---

//21136kb   5168ms#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define gc() getchar()const int N=1e4+5,M=1e6+5;int n,m,S,T,Enum,H[N],to[M],nxt[M],_H[N],_to[M],_nxt[M],in[N],q[N];int tot,bel[N],scc[N][103],num[N],sz[N],Index,dfn[N],low[N],sk[N],top;double A[105][105],E[N],out[N];bool vis[N],vis_s[N],exist[N];inline int read(){    int now=0;register char c=gc();    for(;!isdigit(c);c=gc());    for(;isdigit(c);now=now*10+c-'0',c=gc());    return now;}inline void AddEdge(int u,int v){    to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;    _to[Enum]=u, _nxt[Enum]=_H[v], _H[v]=Enum;}void Tarjan(int x){    dfn[x]=low[x]=++Index, sk[++top]=x, exist[x]=1;    for(int i=H[x]; i; i=nxt[i])        if(!dfn[to[i]]) Tarjan(to[i]),low[x]=std::min(low[x],low[to[i]]);        else if(exist[to[i]]) low[x]=std::min(low[x],dfn[to[i]]);    if(dfn[x]==low[x])    {        ++tot;        do        {            bel[sk[top]]=tot, num[sk[top]]=sz[tot],            scc[tot][sz[tot]++]=sk[top], exist[sk[top--]]=0;        }while(sk[top+1]!=x);    }}void DFS(int x){    vis[x]=vis_s[bel[x]]=1;    if(x==T) return;//有没有都行     for(int i=H[x]; i; i=nxt[i])        if(!vis[to[i]]) /*++in[bel[x]],//Wrong*/DFS(to[i]);}void Gauss(int n){    for(int j=0; j
         
          fabs(A[mxrow][j])) mxrow=i; if(mxrow!=j) for(int k=0; k<=n; ++k) std::swap(A[mxrow][k],A[j][k]); for(int i=j+1; i