走迷宫
Morenan 被困在了一个迷宫里. 迷宫可以视为 N 个点 M 条边的有向图, 其中 Morenan 处于起点 S, 迷宫的终点设为 T. 可惜的是, Morenan 非常的脑小, 他只会从一个点出发随机沿着一条从该点出发的有向边, 到达另一个点. 这样, Morenan 走的步数可能很长, 也可能是无限, 更可能到不了终点. 若到不了终点, 则步数视为无穷大. 但你必须想方设法求出 Morenan 所走步数的期望值.
N<=10000,M<=1000000, 保证强连通分量的大小不超过 100
Clove_unique 的题解
首先考虑图是一个 DAG 的情况
如果除了终点之外还有出度为 0 的点, 那么答案为 INF. 因为有概率不走到终点, 无穷级数里面有∞.
然后令 f(i) 表示从点 i 走到终点的期望步数, 那么 f(i)=∑(i,v)∈E(f(v)+1),?out(i), 其中 out(i) 从点 i 走一条边的概率 (也就是出度的倒数).
如果图不是一个 DAG 的话, 可以缩点之后将图变成一个 DAG, 对于 DAG 上的边直接 dp, 但是强连通分量里的点可以互相到达, 这实际上就是列出了一些方程然后高斯消元.
- CO LD inf=1e18,eps=1e-12;
- CO int N=10000+10,M=100+10;
- vector<int> to[N],rto[N];
- LD out[N];
- int pos[N],dfn,low[N];
- int stk[N],top,ins[N];
- int bln[N],idx;
- vector<int> scc[N];
- void tarjan(int u){
- pos[u]=low[u]=++dfn;
- stk[++top]=u,ins[u]=1;
- for(int i=0;i<(int)to[u].size();++i){
- int v=to[u][i];
- if(!pos[v]){
- tarjan(v);
- low[u]=min(low[u],low[v]);
- }
- else if(ins[v]) low[u]=min(low[u],pos[v]);
- }
- if(low[u]==pos[u]){
- ++idx;
- int x;
- do{
- x=stk[top--],ins[x]=0;
- bln[x]=idx,scc[idx].push_back(x);
- }while(x!=u);
- }
- }
- bool vis[N];
- void dfs(int u){
- vis[u]=1;
- for(int i=0;i<(int)to[u].size();++i){
- int v=to[u][i];
- if(!vis[v]) dfs(v);
- }
- }
- int in[N],tmp[N];
- LD f[N],a[M][M];
- void gauss(int n){
- for(int i=1;i<=n;++i){
- int p=i;
- for(int j=i+1;j<=n;++j)
- if(abs(a[j][i])>abs(a[p][i])) p=j;
- if(p!=i) swap(a[p],a[i]);
- for(int j=1;j<=n;++j)if(j!=i and abs(a[j][i])>eps){
- double coef=-a[j][i]/a[i][i];
- for(int k=i;k<=n+1;++k) a[j][k]+=coef*a[i][k];
- }
- }
- for(int i=1;i<=n;++i) a[i][n+1]/=a[i][i],a[i][i]=1;
- }
- int main(){
- int n=read<int>(),m=read<int>(),s=read<int>(),t=read<int>();
- while(m--){
- int u=read<int>(),v=read<int>();
- to[u].push_back(v),rto[v].push_back(u);
- ++out[u];
- }
- for(int i=1;i<=n;++i) out[i]=1/out[i];
- for(int i=1;i<=n;++i)
- if(!pos[i]) tarjan(i);
- dfs(s);
- if(!vis[t]){
- puts("INF");
- return 0;
- }
- for(int u=1;u<=n;++u)
- for(int i=0;i<(int)rto[u].size();++i){
- int v=rto[u][i];
- if(bln[u]!=bln[v]) ++in[bln[v]];
- }
- for(int i=1;i<=idx;++i)if(i!=bln[t])
- if(!in[i]){
- puts("INF");
- return 0;
- }
- deque<int> Q(1,bln[t]);
- while(Q.size()){
- int x=Q.front();Q.pop_front();
- memset(a,0,sizeof a);
- int num=scc[x].size();
- // cerr<<"scc="<<endl;
- // for(int i=1;i<=num;++i) cerr<<" "<<scc[x][i-1];
- // cerr<<endl;
- for(int i=1;i<=num;++i) tmp[scc[x][i-1]]=i;
- for(int i=1;i<=num;++i){
- int u=scc[x][i-1];
- a[i][i]=1,a[i][num+1]=f[u];
- if(u==t) continue;
- for(int j=0;j<(int)to[u].size();++j){
- int v=to[u][j];
- if(bln[v]!=bln[u]) continue;
- a[i][tmp[v]]-=out[u],a[i][num+1]+=out[u];
- }
- }
- gauss(num);
- for(int i=1;i<=num;++i){
- int u=scc[x][i-1];
- f[u]=a[i][num+1];
- for(int j=0;j<(int)rto[u].size();++j){
- int v=rto[u][j];
- if(bln[v]!=x){
- if(--in[bln[v]]==0) Q.push_back(bln[v]);
- f[v]+=(f[u]+1)*out[v];
- }
- }
- }
- }
- printf("%.3Lf\n",f[s]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3330702.html