bzoj2702[SDOI2012]走迷宫

题意:给你一个有向图,点数10000,边数1000000,SCC大小不超过100(按数据范围的写法只有第三部分数据满足这个条件,不过第二部分数据并没有出现大小大于100个点的SCC,我是用数组大小为100的代码以身试法的2333)从s出发随机走,问走到t的期望步数.

首先考虑inf的情况.如果从s出发可以走到一个无法走到t的点,比如这个数据:红色点为起点,绿色点为终点,那么有1/2的概率永远也走不到(在蓝色点停下).

注意出现环的情况不一定是INF,因为在环上走无穷步的概率可能是无穷小。于是先缩点,把边反向找到所有不能到达t的SCC,如果从s出发有可能到达这样的一个SCC或s本身处于这样一个SCC,那么答案是INF。

接下来,我们把期望步数转化成期望经过的点数(显然经过的边数等于点数-1),那么利用期望的线性性,只需要高斯消元求出每个点的期望经过次数再加起来。但是这个范围显然不能直接做。而SCC大小小于100,提醒我们可以对每个SCC分别进行高斯消元,然后考虑SCC之间的关系。思路类似USACO一道最短路题”道路与航线”,那道题是对每个SCC分别跑dijkstra。

具体的做法:记f[i]为点i的期望经过次数,g[i]为从另一个SCC走到点i的期望次数,因为我们按拓扑序处理每个SCC,所以在处理每个SCC的时候这个SCC中每个点的g[]值都已经求出来了.接下来对SCC中每个点列一个方程.对于点x,f[x]=g[x]+sigma(f[j]/outdeg[j]),j向x有一条有向边且j和x在同一个SCC,outdeg为出度。这里j可以等于x(有自环),验证一下,这时候方程也是对的.解完这个SCC之后要用这个SCC里的点更新其他SCC的g[].注意边界g[s]=1,f[t]=1

然后码码码就好了。

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int n,m,s,t;
const int maxn=10005,maxm=1000005;
//Graph Theory
struct edge{
  int to,next;
}lst1[maxm],lst2[maxm],lst3[maxm];int len1=1,len2=1,len3=1;
int first1[maxn],first2[maxn],first3[maxn];
void addedge1(int a,int b){
  lst1[len1].to=b;lst1[len1].next=first1[a];
  first1[a]=len1++;
}
void addedge2(int a,int b){
  lst2[len2].to=b;lst2[len2].next=first2[a];
  first2[a]=len2++;
}
void addedge3(int a,int b){
  lst3[len3].to=b;lst3[len3].next=first3[a];
  first3[a]=len3++;
}
int outdeg[maxn];
int belong[maxn],tot,sz[maxn];
vector<int> scc[maxn];
int stk[maxn],top,dfn[maxn],low[maxn],T;
bool ins[maxn];
namespace Trajan{
  void dfs(int x){
    low[x]=dfn[x]=++T;
    stk[top++]=x;ins[x]=true;
    for(int pt=first1[x];pt;pt=lst1[pt].next){
      if(!dfn[lst1[pt].to]){
    dfs(lst1[pt].to);
    if(low[lst1[pt].to]<low[x])low[x]=low[lst1[pt].to];
      }else if(ins[lst1[pt].to]&&dfn[lst1[pt].to]<low[x])low[x]=dfn[lst1[pt].to];
    }
    if(dfn[x]==low[x]){
      ++tot;
      do{
    ins[stk[--top]]=false;
    belong[stk[top]]=tot;
    scc[tot].push_back(stk[top]);
    sz[tot]++;
      }while(stk[top]!=x);
    }
  }
  void tarjan(){
    for(int i=1;i<=n;++i){
      if(!dfn[i])dfs(i);
    }
    for(int i=1;i<=n;++i){
      for(int pt=first1[i];pt;pt=lst1[pt].next){
    if(belong[lst1[pt].to]!=belong[i]){
      addedge2(belong[lst1[pt].to],belong[i]);
      addedge3(belong[i],belong[lst1[pt].to]);
    }
      }
    }
  }
  bool reachfromend[maxn],mustreachend[maxn];
  void predfs(int x){
    reachfromend[x]=true;
    for(int pt=first2[x];pt;pt=lst2[pt].next){
      if(!reachfromend[lst2[pt].to]){
    predfs(lst2[pt].to);
      }
    }
  }
  bool checkdfs(int x){
    if(!reachfromend[x])return false;
    for(int pt=first3[x];pt;pt=lst3[pt].next){
      if(mustreachend[lst3[pt].to])continue;
      if(!checkdfs(lst3[pt].to))return false;
    }
    return mustreachend[x]=true;
  }
  bool check(){
    predfs(belong[t]);
    return checkdfs(belong[s]);
  }
};
double f[maxn],g[maxn];
int map[maxn];
namespace Work{
  bool done[maxn];
  double F[105][105];
  int rk;
  void Swap(int a,int b){
    for(int i=0;i<=rk;++i)swap(F[a][i],F[b][i]);
  }
  void multplus(int a,int b,double times){
    for(int i=0;i<=rk;++i)F[a][i]+=F[b][i]*times;
  }
  void Gauss(int n){
    rk=n;
    for(int i=1;i<=n;++i){
      if(F[i][i]==0){
    for(int j=i+1;j<=n;++j){
      if(F[j][i]!=0){
        Swap(i,j);break;
      }
    }
      }
      for(int j=i+1;j<=n;++j)multplus(j,i,-F[j][i]/F[i][i]);
    }
    for(int i=n;i>=1;--i){
      F[i][0]/=F[i][i];
      for(int j=i-1;j>=1;--j){
    F[j][0]-=F[j][i]*F[i][0];
      }
    }
  }
  void build_equations(int x){
    for(int i=1;i<=sz[x];++i){
      for(int j=0;j<=sz[x];++j){
    F[i][j]=0;
      }
    }
    for(int i=0;i<sz[x];++i)F[i+1][0]=-g[scc[x][i]];
    for(int i=1;i<=sz[x];++i){
      F[i][i]=-1;map[scc[x][i-1]]=i;
      if(scc[x][i-1]==t)F[i][0]=-1;
    }
    for(int i=0;i<sz[x];++i){
      if(scc[x][i]==t)continue;
      for(int pt=first1[scc[x][i]];pt;pt=lst1[pt].next){
    if(belong[lst1[pt].to]==x){
      if(lst1[pt].to==t)continue;
      F[map[lst1[pt].to]][i+1]+=1.0/outdeg[scc[x][i]];
    }
      }
    }

  }
  void dfs(int x){
    for(int pt=first2[x];pt;pt=lst2[pt].next){
      if(!done[lst2[pt].to])dfs(lst2[pt].to);
    }
    build_equations(x);
    Gauss(sz[x]);
    for(int i=0;i<sz[x];++i){
      f[scc[x][i]]=F[i+1][0];
    }
    for(int i=0;i<sz[x];++i){
      for(int pt=first1[scc[x][i]];pt;pt=lst1[pt].next){
    if(belong[lst1[pt].to]!=x){
      g[lst1[pt].to]+=f[scc[x][i]]/outdeg[scc[x][i]];
    }
      }
    }
    done[x]=true;
  }
}
int main(){
  scanf("%d%d%d%d",&n,&m,&s,&t);
  int a,b;
  for(int i=1;i<=m;++i){
    scanf("%d%d",&a,&b);addedge1(a,b);
    outdeg[a]++;
  }
  Trajan::tarjan();
  if(Trajan::check()){
    g[s]=1;
    Work::dfs(belong[t]);
    double ans=0;
    for(int i=1;i<=n;++i){//printf("%.2f ",f[i]);
      ans+=f[i];
    }//ans:the expected number of points on the path from s to t
    printf("%.3f\n",ans-1);
  }else{
    printf("INF\n");
  }
  return 0;
}
时间: 12-23

bzoj2702[SDOI2012]走迷宫的相关文章

SDOI2012 走迷宫

走迷宫 Morenan被困在了一个迷宫里.迷宫可以视为N个点M条边的有向图,其中Morenan处于起点S,迷宫的终点设为T.可惜的是,Morenan非常的脑小,他只会从一个点出发随机沿着一条从该点出发的有向边,到达另一个点.这样,Morenan走的步数可能很长,也可能是无限,更可能到不了终点.若到不了终点,则步数视为无穷大.但你必须想方设法求出Morenan所走步数的期望值. N<=10000,M<=1000000,保证强连通分量的大小不超过100 Clove_unique的题解 首先考虑图是

bzoj 2707 [SDOI2012]走迷宫(SCC+高斯消元)

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

NYOJ306 走迷宫(dfs+二分搜索)

题目描述 http://acm.nyist.net/JudgeOnline/problem.php?pid=306 Dr.Kong设计的机器人卡多非常爱玩,它常常偷偷跑出实验室,在某个游乐场玩之不疲.这天卡多又跑出来了,在SJTL游乐场玩个不停,坐完碰碰车,又玩滑滑梯,这时卡多又走入一个迷宫.整个迷宫是用一个N * N的方阵给出,方阵中单元格中填充了一个整数,表示走到这个位置的难度. 这个迷宫可以向上走,向下走,向右走,向左走,但是不能穿越对角线.走迷宫的取胜规则很有意思,看谁能更快地找到一条路

青蛙走迷宫问题(体力值)

题目: 青蛙走迷宫,1代表路通,0代表不通:起点是(0, 0),终点是(0,m - 1);青蛙每次向上走需要消耗体力值为3,向下走不消耗体力值,平走消耗体力值1:根据给定值判断青蛙是否可以根据初始值到达终点,并求出消耗体力值最少的路径: 举例: n = 4, m =4, p = 10(体力值) 4 4 10 1 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1 则结果为:[[0, 0], [1, 0], [1, 1], [2, 1], [2, 2], [2, 3], [1, 3], [

深度优先算法——走迷宫的实现

深度优先搜索算法(Depth-First-Search),是搜索算法的一种.是沿着树的深度遍历树的节点,尽可能深的搜索树的分支.当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点.这一过程一直进行到已发现从源节点可达的所有节点为止.如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止.属于盲目搜索. 深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用拓扑排序表可以方便的解决很多相关的图

走迷宫

走迷宫 时限:1000ms 内存限制:10000K  总时限:3000ms 描述 判断是否能从迷宫的入口到达出口 输入 先输入两个整数表示迷宫的行数m和列数n,再输入口和出口的坐标,最后分m行输入迷宫,其中1表示墙,0表示空格每个数字之间都有空格. 输出 若能到达,则输出"Yes",否则输出"No",结果占一行. 输入样例 3 30 02 20 0 01 1 00 1 0 输出样例 Yes #include <iostream> using namesp

【老鼠走迷宫二】

/* 老鼠走迷宫二 有问题 */ #include <stdio.h> #include <stdlib.h> void visit(int ,int); int maze[9][9] = { {2, 2, 2, 2, 2, 2, 2, 2, 2}, {2, 0, 0, 0, 0, 0, 0, 0, 2}, {2, 0, 2, 2, 0, 2, 2, 0, 2}, {2, 0, 2, 0, 0, 2, 0, 0, 2}, {2, 0, 2, 0, 2, 0, 2, 0, 2}, {

算法:老鼠走迷宫问题

算法:老鼠走迷宫问题(初) [写在前面] 老鼠走迷宫问题的递归实现,是对递归思想的一种应用. [问题描述] 给定一个二维数组,数组中2表示墙壁,0表示通路,由此数组可展示为一个迷宫图.给定入口位置和出口位置,判断之间是否存在通路并显示出走出迷宫的道路. [代码] 对题目的描述部分 int migo[7][7]={ {2, 2, 2, 2, 2, 2, 2}, {2, 0, 0, 0, 0, 0, 2}, {2, 0, 2, 0, 2, 0, 2}, {2, 0, 0, 0, 0, 2, 2},

数据结构之深度优先搜索(走迷宫)

在此以走迷宫为例: 给定迷宫起点和终点,看能否到达:(xt,yt) void f(int x,int y){ if(x<0||x>21||y<0||y>21){//判断是否超出迷宫 return; } ch[x][y]='#'; for(i=0;i<4;i++){if(ch[x][y]=='.'){ if(x==xt+1&&y==yt+1){ flag=1; return ; } //四个方向 f(x,y+1); f(x,y-1); f(x+1,y); f(x