频道栏目
首页 > 考试 > 其他 > 正文

走迷宫(tarjan缩点+拓扑+概率期望+gauss)

2018-03-07 02:49:23      个评论    来源:Coco_T的博客  
收藏   我要投稿

Description

Morenan被困在了一个迷宫里。迷宫可以视为N个点M条边的有向图,其中Morenan处于起点S,迷宫的终点设为T。可惜的是,Morenan非常的脑小,他只会从一个点出发随机沿着一条从该点出发的有向边,到达另一个点。这样,Morenan走的步数可能很长,也可能是无限,更可能到不了终点。若到不了终点,则步数视为无穷大。但你必须想方设法求出Morenan所走步数的期望值。

Input

第1行4个整数,N,M,S,T
第[2, M+1]行每行两个整数o1, o2,表示有一条从o1到o2的边。

Output

一个浮点数,保留小数点3位,为步数的期望值。若期望值为无穷大,则输出”INF”。

Sample Input 1

6 6 1 6
1 2
1 3
2 4
3 5
4 6
5 6

Sample Output 1

3.000

Sample Input 2

9 12 1 9
1 2
2 3
3 1
3 4
3 7
4 5
5 6
6 4
6 7
7 8
8 9
9 7

Sample Output 2

9.500

Sample Input 3

2 0 1 2

Sample Output 3

INF

Hint

这里写图片描述

分析:

对于原图中的点(逆推):
E(from)=(E(to)+1)out[from]" role="presentation">E(from)=(E(to)+1)out[from]
其中out[i]" role="presentation">out[i]表示i" role="presentation">i的出度

对于图中的强连通分量,我们用tarjan缩成点
得到一个DAG,逆向拓扑这个DAG
因为是逆推,所以DAG的边我们反着连就好了
我们在拓扑排序的时候,顺便维护:E(from)=(E(to)+1)out[from]" role="presentation">E(from)=(E(to)+1)out[from]
这样就可以得到scc中一些点的概率

由于在一个强连通分量中,点与点之间是可以互相到达的
所以我们就可以通过这些已知的点的概率,推出整个scc中每个点的概率
用gauss消元即可

关于题目中提到的INF:
题中说的到不了终点不是单纯的说起点和终点不连通
而是说如果有一条路无论如何都到不了终点,那么在走的过程中如果选择了这条路,那么这条路的期望就是INF,对于总的答案来说也是INF
所以我们在缩点之后形成的有向无环图中,如果出度为0的点不只T或者不是T,那么对于期望步数来说就是INF

#include

using namespace std;

const double eps=1e-8;
const int M=1000005;
const int N=10005;
struct node{
    int x,y,nxt;
};
node way[M],e[M];
int n,m,start,ed,st[N],tot=0,ste[N],tet=0;
int du[N];
double E[N],out[N],f[N];

void add(int u,int w) {
    tot++;way[tot].x=u;way[tot].y=w;way[tot].nxt=st[u];st[u]=tot;
    tet++;e[tet].x=w;e[tet].y=u;e[tet].nxt=ste[w];ste[w]=tet;
}

int low[N],dfn[N],clo=0,S[N],top=0,cnt=0,belong[N],scc[N][105],num[N];
bool vis[N],ext[N];

void tarjan(int now) {
    S[++top]=now;
    vis[now]=1;      //入栈标记 
    low[now]=dfn[now]=++clo;
    for (int i=st[now];i;i=way[i].nxt)
        if (!dfn[way[i].y]) {
            tarjan(way[i].y);
            low[now]=min(low[now],low[way[i].y]);
        }
        else if (vis[way[i].y]) {
            low[now]=min(low[now],dfn[way[i].y]);
        }

    if (low[now]==dfn[now]) {
        cnt++;
        int x=0;
        while (x!=now)
        {
            x=S[top--];
            belong[x]=cnt;
            vis[x]=0;
            scc[cnt][++scc[cnt][0]]=x;
            num[x]=scc[cnt][0];
        }
    }
}

double a[105][105];

void gauss(int n) {
    int now=1,to;
    for (int i=1;i<=n;i++) {
        for (to=now;to<=n;to++)
            if (fabs(a[to][i])>eps) break;
        if (to>n) continue;
        if (to!=now)
            for (int j=1;j<=n+1;j++)
                swap(a[to][j],a[now][j]);
        for (int j=1;j<=n;j++)
            if (j!=now) {
                double t=a[j][i]/a[now][i];
                for (int k=1;k<=n+1;k++)
                    a[j][k]-=t*a[now][k];
            }
        now++;
    }
    for (int i=1;i<=n;i++) a[i][n+1]/=a[i][i];
}

void TOP(){                               //top  DAG
    int tou,wei;
    tou=wei=0;
    S[++wei]=belong[ed];
    while (tou
                                
            
        
       
上一篇:数组元素循环右移问题解析
下一篇:K-diff Pairs in an Array:统计数组中差值为K的元素对
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站