测试地址：走迷宫
题目大意：有一个个点的有向图，人从起点出发，每次等概率随机选择一条出边走出，问走到终点的期望步数。，一个强连通分量中的点数不超过。
做法：本题需要用到SCC缩点+拓扑排序+期望DP+高斯消元。
我们很快就能根据标准的期望逆推型DP得到该题的状态转移方程，因为图中存在环，所以需要高斯消元，然而的时间复杂度显然会炸。这时数据范围里的提示已经剧透了做法的一部分：强连通分量。
注意到把强连通分量缩起来后，整个图是一个DAG，而DAG上的点的期望只跟它出边连向的点有关。那么我们对于两个强连通分量之间的边，就直接算出它们的贡献，而对于一个强连通分量中的点，用高斯消元即可。
还值得注意的一点是INF的判断，如果从起点根本走不到终点，或者能从起点走到一个走不到终点的点，那么期望步数就是INF。
以上算法的时间复杂度为（为强连通分量的大小），因为高斯消元常数很小，所以可以通过此题。
我傻逼的地方：我居然把Tarjan算法求SCC写错了……下个礼拜就省选了，怕不是要凉了……
以下是本人代码：
#include <bits/stdc++.h>
using namespace std;
int n,m,S,T,a[1000010],b[1000010],first[20010]={0},tot=0;
int top,st[20010],dfn[20010],low[20010],tim=0,belong[20010]={0},scc;
int h,t,q[20010],totp=0,pos[20010],qpos[20010],l[20010],r[20010],in[20010]={0},sccout[20010]={0};
bool vis[20010]={0},inst[20010]={0};
long double out[20010]={0},p[20010],g[210][210];
struct edge
{
int v,next;
}e[2000010];
void insert(int a,int b)
{
e[++tot].v=b;
e[tot].next=first[a];
first[a]=tot;
}
void init()
{
scanf("%d%d%d%d",&n,&m,&S,&T);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a[i],&b[i]);
insert(a[i],b[i]);
out[a[i]]+=1.0;
}
scc=n;
}
void tarjan(int v)
{
dfn[v]=low[v]=++tim;
st[++top]=v;
vis[v]=inst[v]=1;
int now=top;
for(int i=first[v];i;i=e[i].next)
{
if (!vis[e[i].v])
{
tarjan(e[i].v);
low[v]=min(low[v],low[e[i].v]);
}
else if (inst[e[i].v]) low[v]=min(low[v],dfn[e[i].v]);
}
if (dfn[v]==low[v])
{
scc++;
l[scc]=totp+1;
while(top>=now)
{
belong[st[top]]=scc;
pos[++totp]=st[top];
inst[st[top]]=0;
top--;
}
r[scc]=totp;
}
}
void toposort()
{
h=t=1;
for(int i=1;i<=m;i++)
if (belong[a[i]]&&belong[b[i]]&&belong[a[i]]!=belong[b[i]])
insert(belong[a[i]],belong[b[i]]),in[belong[b[i]]]++,sccout[belong[a[i]]]++;
q[1]=belong[S];
while(h<=t)
{
int v=q[h++];
for(int i=first[v];i;i=e[i].next)
{
in[e[i].v]--;
if (!in[e[i].v]) q[++t]=e[i].v;
}
}
}
void gauss(int n)
{
for(int i=1;i<=n;i++)
{
int mx=i;
for(int j=i+1;j<=n;j++)
if (fabs(g[j][i])>fabs(g[mx][i])) mx=j;
for(int j=i;j<=n+1;j++)
swap(g[i][j],g[mx][j]);
for(int j=i+1;j<=n;j++)
{
for(int k=i+1;k<=n+1;k++)
g[j][k]-=g[j][i]*g[i][k]/g[i][i];
g[j][i]=0.0;
}
}
for(int i=n;i>=1;i--)
for(int j=1;j<i;j++)
{
g[j][n+1]-=g[j][i]*g[i][n+1]/g[i][i];
g[j][i]=0.0;
}
}
void work()
{
for(int i=n+1;i<=scc;i++)
if (i!=belong[T]&&!sccout[i]) {printf("INF");return;}
p[T]=0.0;
for(int i=t;i>=1;i--)
{
int v=q[i];
memset(g,0,sizeof(g));
for(int j=l[v];j<=r[v];j++)
qpos[pos[j]]=j-l[v]+1;
for(int j=l[v];j<=r[v];j++)
{
int x=pos[j];
if (x==T) {g[qpos[x]][qpos[x]]+=1.0;continue;}
for(int k=first[x];k;k=e[k].next)
{
int y=e[k].v;
if (y==T||belong[e[k].v]!=v) g[qpos[x]][r[v]-l[v]+2]+=p[y]+1.0;
else
{
g[qpos[x]][qpos[y]]-=1.0;
g[qpos[x]][r[v]-l[v]+2]+=1.0;
}
}
for(int k=1;k<=r[v]-l[v]+2;k++)
g[qpos[x]][k]/=out[x];
g[qpos[x]][qpos[x]]+=1.0;
}
gauss(r[v]-l[v]+1);
for(int j=l[v];j<=r[v];j++)
p[pos[j]]=g[j-l[v]+1][r[v]-l[v]+2]/g[j-l[v]+1][j-l[v]+1];
}
printf("%.3Lf",p[S]);
}
int main()
{
init();
tarjan(S);
toposort();
work();
return 0;
}