<label id="m7x0d"></label>

[BZOJ2707][SDOI2012]走迷宮（tarjan+概率期望+高斯消元）

2019-11-06 08:15:45

字體：大中小

來源：轉載

供稿：網友

題目描述

傳送門

題解

剛開始題意理解錯了…或者說我對期望的理解本來就不是很好… 首先考慮圖是一個DAG的情況如果除了終點之外還有出度為0的點，那么答案為INF（因為有概率不走到終點）然后令f(i) $f(i)$ 表示從點i走到終點的期望步數，那么f(i)=∑(i,v)∈E(f(v)+1)?out(i) $f(i)=/sum/limits_{(i,v)/in E}(f(v)+1)*out(i)$ ，其中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]]; } } }