BZOJ.2707.[SDOI2012]走迷宫(期望 Tarjan 高斯消元)

题目链接

一个点到达终点的期望步数 \(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 <cmath> #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> #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<n; ++j){int mxrow=j;for(int i=j+1; i<n; ++i)if(fabs(A[i][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<n; ++i)if(A[i][j]){double t=A[i][j]/A[j][j];for(int k=j; k<=n; ++k)A[i][k]-=A[j][k]*t;}}for(int i=n-1; ~i; --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() {n=read(),m=read(),S=read(),T=read();for(int u,v,i=1; i<=m; ++i) u=read(),v=read(),out[u]+=1.0,AddEdge(u,v);for(int i=1; i<=n; ++i)if(!dfn[i]) Tarjan(i);DFS(S);if(!vis[T]) {puts("INF"); return 0;}for(int x=1; x<=n; ++x)for(int i=H[x]; i; i=nxt[i])if(bel[x]!=bel[to[i]]) ++in[bel[x]];//反向图上的入度+1。for(int i=1; i<=tot; ++i)if(vis_s[i]&&!in[i]&&bel[T]!=i) {puts("INF"); return 0;}for(int i=1; i<=n; ++i) out[i]=1.0/out[i];int h=0,t=0;q[t++]=bel[T]; // for(int i=1; i<=tot; ++i) // if(!in[i]) q[t++]=i;//in[]=0的只能是bel[T].while(h<t){int now=q[h++];memset(A,0,sizeof A);for(int j=0; j<sz[now]; ++j){int x=scc[now][j];A[j][j]=1.0, A[j][sz[now]]=E[x]/*之前加上的*/;if(x==T) continue;//不计算终点连出的边！for(int i=H[x]; i; i=nxt[i])if(bel[to[i]]==now){A[j][sz[now]]+=out[x],//步数+1.A[j][num[to[i]]]-=out[x];//是点的出度不是in[]! //-=不能直接赋值=：有重边！}}Gauss(sz[now]);for(int j=0; j<sz[now]; ++j){int x=scc[now][j];E[x]=A[j][sz[now]];for(int i=_H[x]; i; i=_nxt[i])if(bel[_to[i]]!=now){if(!--in[bel[_to[i]]]) q[t++]=bel[_to[i]];E[_to[i]]+=(E[x]+1)*out[_to[i]];}}}printf("%.3lf",E[S]);return 0; }

转载于:https://www.cnblogs.com/SovietPower/p/8681877.html

总结

以上是生活随笔为你收集整理的BZOJ.2707.[SDOI2012]走迷宫(期望 Tarjan 高斯消元)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。