http://www.lydsy.com/JudgeOnline/problem.php?id=2707
dp[i] 表示从点i到终点的期望步数
dp[i]= Σ (dp[j]+1)/out[i]
j表示i的出边指向的店，out[i] 表示i的出边数
如果图是一张DAG，那么直接在反图 上 拓扑排序DP即可
现在有环，那就缩点，环上的用高斯消元
无解的情况：
1、起点走不到终点
2、存在一个联通块，起点能走到他，但这个联通块没有出边，且不是终点所在的联通块
因为此时一旦步入这个联通块将永远走不出去
#include<cmath> #include<cstdio> #include<vector> #include<queue> #include<cstring> #include<algorithm> #include<iostream> #define N 10001 #define M 1000001 using namespace std; int front[N],to[M],nxt[M],tot; int front_[N],to_[M],nxt_[M],tot_; int dfn[N],low[N],id; int st[N],top; bool vis[N]; vector<int>block[N]; int bl[N],cnt; int num[N]; double out[N]; int in_[N]; bool vis_block[N]; double a[101][101],dp[N]; queue<int>q; void read(int &x) { x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } } void add(int u,int v) { to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; to_[++tot_]=u; nxt_[tot_]=front_[v]; front_[v]=tot_; } void tarjan(int x) { dfn[x]=low[x]=++id; st[++top]=x; vis[x]=true; for(int i=front[x];i;i=nxt[i]) if(!dfn[to[i]]) { tarjan(to[i]); low[x]=min(low[x],low[to[i]]); } else if(vis[to[i]]) low[x]=min(low[x],dfn[to[i]]); if(dfn[x]==low[x]) { cnt++; while(st[top]!=x) { block[cnt].push_back(st[top]); bl[st[top]]=cnt; num[st[top]]=block[cnt].size()-1; vis[st[top--]]=false; } block[cnt].push_back(x); bl[x]=cnt; num[x]=block[cnt].size()-1; vis[st[top--]]=false; } } void dfs(int x) { vis[x]=vis_block[bl[x]]=true; for(int i=front[x];i;i=nxt[i]) if(!vis[to[i]]) dfs(to[i]); } void gauss(int n) { int r; double t; for(int i=0;i<n;++i) { r=i; for(int j=i+1;j<n;++j) if(fabs(a[j][i])>fabs(a[r][i])) r=j; if(r!=i) for(int j=0;j<=n;++j) swap(a[r][j],a[i][j]); for(int k=i+1;k<n;++k) { t=a[k][i]/a[i][i]; for(int j=i;j<=n;++j) a[k][j]-=t*a[i][j]; } } for(int i=n-1;i>=0;--i) { for(int j=i+1;j<n;++j) a[i][n]-=a[i][j]*a[j][n]; a[i][n]/=a[i][i]; } } int main() { int n,m,s,t; read(n); read(m); read(s); read(t); int u,v; for(int i=1;i<=m;++i) { read(u); read(v); add(u,v); out[u]++; } for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i); dfs(s); if(!vis[t]) { printf("INF"); return 0; } for(int i=1;i<=n;++i) for(int j=front[i];j;j=nxt[j]) if(bl[i]!=bl[to[j]]) in_[bl[i]]++; for(int i=1;i<=cnt;++i) if(vis_block[i] && !in_[i] && i!=bl[t]) { printf("INF"); return 0; } for(int i=1;i<=n;++i) out[i]=1.0/out[i]; q.push(bl[t]); int now,siz,x; while(!q.empty()) { now=q.front(); q.pop(); memset(a,0,sizeof(a)); siz=block[now].size(); for(int i=0;i<siz;++i) { x=block[now][i]; a[i][i]=1; a[i][siz]=dp[x]; if(x==t) continue; for(int j=front[x];j;j=nxt[j]) if(bl[to[j]]==now) { a[i][siz]+=out[x]; a[i][num[to[j]]]-=out[x]; } } gauss(siz); for(int i=0;i<siz;++i) { x=block[now][i]; dp[x]=a[i][siz]; for(int j=front_[x];j;j=nxt_[j]) if(bl[to_[j]]!=now) { --in_[bl[to_[j]]]; if(!in_[bl[to_[j]]]) q.push(bl[to_[j]]); dp[to_[j]]+=(dp[x]+1)*out[to_[j]]; } } } printf("%.3lf",dp[s]); }