题目描述
传送门
题解
刚开始题意理解错了…或者说我对期望的理解本来就不是很好…
首先考虑图是一个DAG的情况
如果除了终点之外还有出度为0的点，那么答案为INF（因为有概率不走到终点）
然后令f(i)表示从点i走到终点的期望步数，那么f(i)=∑(i,v)∈E(f(v)+1)∗out(i)，其中out(i)从点i走一条边的概率（也就是出度的倒数）
如果图不是一个DAG的话，可以缩点之后将图变成一个DAG，对于DAG上的边直接dp，但是强连通分量里的点可以互相到达，这实际上就是列出了一些方程然后高斯消元
代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
const double INF=1e18;
const double eps=1e-12;
int n,m,s,t,dfs_clock,top,scc;
struct data{int x,y;}e[1000005];
int tot,point[10005],nxt[1000005],v[1000005];
int _tot,_point[10005],_nxt[1000005],_v[1000005];
int dfn[10005],low[10005],stack[10005],belong[10005];bool vis[10005];
int pt[10005][105],cnt[10005],num[10005],in[10005];
double out[10005],a[105][105],b[105],ans[105],f[10005];
queue <int> q;
void add(int x,int y)
{
++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;
++_tot; _nxt[_tot]=_point[y]; _point[y]=_tot; _v[_tot]=x;
}
void tarjan(int x)
{
dfn[x]=low[x]=++dfs_clock;stack[++top]=x;vis[x]=1;
for (int i=point[x];i;i=nxt[i])
if (!dfn[v[i]])
{
tarjan(v[i]);
low[x]=min(low[x],low[v[i]]);
}
else if (vis[v[i]])
low[x]=min(low[x],dfn[v[i]]);
if (dfn[x]==low[x])
{
int now=0;++scc;
while (now!=x)
{
now=stack[top--];
pt[scc][++cnt[scc]]=now;
num[now]=cnt[scc];
belong[now]=scc;
vis[now]=0;
}
}
}
void gauss(int n)
{
for (int i=1;i<=n;++i)
{
int num=i;
for (int j=i+1;j<=n;++j)
if (fabs(a[j][i])>fabs(a[num][i])) num=j;
if (num!=i)
{
for (int j=1;j<=n;++j) swap(a[num][j],a[i][j]);
swap(b[num],b[i]);
}
for (int j=i+1;j<=n;++j)
if (fabs(a[j][i])>eps)
{
double t=a[j][i]/a[i][i];
for (int k=1;k<=n;++k)
a[j][k]-=a[i][k]*t;
b[j]-=b[i]*t;
}
}
for (int i=n;i>=1;--i)
{
for (int j=i+1;j<=n;++j) b[i]-=ans[j]*a[i][j];
ans[i]=b[i]/a[i][i];
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
for (int i=1;i<=m;++i)
{
scanf("%d%d",&e[i].x,&e[i].y);
add(e[i].x,e[i].y);out[e[i].x]+=1.0;
}
for (int i=1;i<=n;++i) out[i]=1.0/out[i];
for (int i=1;i<=n;++i)
if (!dfn[i]) tarjan(i);
for (int i=1;i<=m;++i)
if (belong[e[i].x]!=belong[e[i].y])
++in[belong[e[i].x]];
for (int i=1;i<=scc;++i)
if (belong[t]!=i&&!in[i])
{
puts("INF");
return 0;
}
q.push(belong[t]);
while (!q.empty())
{
int now=q.front();q.pop();
memset(a,0,sizeof(a));memset(b,0,sizeof(b));
memset(ans,0,sizeof(ans));
for (int i=1;i<=cnt[now];++i)
{
int x=pt[now][i];
a[i][i]=1.0;
if (f[x]) b[i]=f[x];
if (x==t) continue;
for (int j=point[x];j;j=nxt[j])
if (belong[v[j]]==now)
{
b[i]+=out[x];
a[i][num[v[j]]]-=out[x];
}
}
gauss(cnt[now]);
for (int i=1;i<=cnt[now];++i)
{
int x=pt[now][i];
f[x]=ans[i];
for (int j=_point[x];j;j=_nxt[j])
if (belong[_v[j]]!=now)
{
--in[belong[_v[j]]];
if (!in[belong[_v[j]]]) q.push(belong[_v[j]]);
f[_v[j]]+=(f[x]+1.0)*out[_v[j]];
}
}
}
PRintf("%.3lf\n",f[s]);
return 0;
}
