BZOJ 2707: [SDOI2012]走迷宫( tarjan + 高斯消元 )

时间:2022-08-26 20:50:17

BZOJ 2707: [SDOI2012]走迷宫( tarjan + 高斯消元 )

数据范围太大不能直接高斯消元, tarjan缩点然后按拓扑逆序对每个强连通分量高斯消元就可以了.

E(u) = 1 + Σ E(v) / degree(u)

对拍时发现网上2个程序的INF判断和我不一样(他们2个的INF判断也不一样).....然而都A掉了....我觉得应该是他们写错了,我的做法应该没错的(正反2遍dfs,GDOI2015day1t1大冒险)(求打脸

------------------------------------------------------------------------

#include<cmath>
#include<stack>
#include<cstdio>
#include<cstring>
#include<algorithm>
 
using namespace std;
 
const int maxn = 10009;
const int maxb = 209;
const double eps = 1e-8;
 
int N, S, T, deg[maxn];
int dfn[maxn], low[maxn], sz[maxn], CK;
int scc[maxn], Scc[maxn][maxb], Id[maxn], n;
bool F[maxn];
stack<int> stk;
double ans[maxn], mat[maxb][maxb];
 
inline void Min(int &x, int t) {
if(t < x) x = t;
}
 
struct edge {
int t;
edge* n;
} E[5000000], *pt = E;
 
struct G {
edge* H[maxn];
bool vis[maxn];
inline void AddEdge(int u, int v) {
pt->t = v, pt->n = H[u], H[u] = pt++;
}
void dfs(int x) {
vis[x] = true;
for(edge* e = H[x]; e; e = e->n)
if(!vis[e->t]) dfs(e->t);
}
void DFS(int x) {
memset(vis, 0, sizeof vis);
dfs(x);
}
} g[3];
 
void tarjan(int x) {
dfn[x] = low[x] = ++CK;
stk.push(x);
for(edge* e = g[0].H[x]; e; e = e->n) if(!dfn[e->t]) {
tarjan(e->t);
Min(low[x], low[e->t]);
} else if(!~scc[e->t])
Min(low[x], dfn[e->t]);
if(dfn[x] == low[x]) {
int t;
do {
t = stk.top(); stk.pop();
scc[t] = n;
Id[t] = sz[n];
Scc[n][sz[n]++] = t;
} while(t != x);
n++;
}
}
 
void Init() {
int m, u, v;
scanf("%d%d%d%d", &N, &m, &S, &T);
S--, T--;
memset(deg, 0, sizeof deg);
while(m--) {
scanf("%d%d", &u, &v);
u--, v--;
if(u == T) continue;
g[0].AddEdge(u, v);
deg[u]++;
}
}
 
void Solve(int x) {
if(x == scc[T]) {
ans[T] = 0;
return;
}
for(int i = 0; i < sz[x]; i++) {
for(int j = 0; j < sz[x]; j++) mat[i][j] = 0;
mat[i][sz[x]] = deg[Scc[x][i]];
for(edge* e = g[0].H[Scc[x][i]]; e; e = e->n)
if(scc[e->t] == x) {
mat[i][Id[e->t]]--;
} else if(e->t != T)
mat[i][sz[x]] += ans[e->t];
mat[i][i] += deg[Scc[x][i]];
}
for(int i = 0, r; i < sz[x]; i++) {
r = i;
for(int j = i; ++j < sz[x]; )
if(fabs(mat[j][i]) > fabs(mat[r][i])) r = j;
if(r != i) {
for(int j = 0; j <= sz[x]; j++)
swap(mat[i][j], mat[r][j]);
}
for(int j = i; ++j < sz[x]; ) {
double t = mat[j][i] / mat[i][i];
for(int k = i; k <= sz[x]; k++)
mat[j][k] -= t * mat[i][k];
}
}
for(int i = sz[x]; i--; ) {
for(int j = i; ++j < sz[x]; )
mat[i][sz[x]] -= mat[j][sz[x]] * mat[i][j];
mat[i][sz[x]] /= mat[i][i];
}
for(int i = 0; i < sz[x]; i++)
ans[Scc[x][i]] = mat[i][sz[x]];
}
 
void dfs(int x) {
for(edge* e = g[1].H[x]; e; e = e->n)
if(!F[e->t]) dfs(e->t);
F[x] = true;
Solve(x);
}
 
void Work() {
if(S == T) {
puts("0.000");
return;
}
memset(dfn, 0, sizeof dfn);
memset(scc, -1, sizeof scc);
memset(sz, 0, sizeof sz);
CK = n = 0;
for(int i = 0; i < N; i++)
if(!dfn[i]) tarjan(i);
for(int i = 0; i < N; i++)
for(edge* e = g[0].H[i]; e; e = e->n) if(scc[i] != scc[e->t]) {
g[1].AddEdge(scc[i], scc[e->t]);
g[2].AddEdge(scc[e->t], scc[i]);
}
g[1].DFS(scc[S]), g[2].DFS(scc[T]);
for(int i = 0; i < n; i++) if(g[1].vis[i] && !g[2].vis[i]) {
puts("INF"); return;
}
memset(F, 0, sizeof F);
dfs(scc[S]);
printf("%.3lf\n", ans[S]);
}
 
int main() {
Init();
Work();
return 0;
}

------------------------------------------------------------------------

2707: [SDOI2012]走迷宫

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 372  Solved: 149
[Submit][Status][Discuss]

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"。
【样例输入1】
6 6 1 6
1 2
1 3
2 4
3 5
4 6
5 6
【样例输出1】
3.000
【样例输入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
【样例输出2】
9.500
【样例输入3】
2 0 1 2
【样例输出3】
INF
【数据范围】
测试点
N
M
Hint
[1, 6]
<=10
<=100
 
[7, 12]
<=200
<=10000
 
[13, 20]
<=10000
<=1000000
保证强连通分量的大小不超过100
 
 
另外,均匀分布着40%的数据,图中没有环,也没有自环

Sample Input

Sample Output

HINT

Source

BZOJ 2707: [SDOI2012]走迷宫( tarjan + 高斯消元 )的更多相关文章

  1. BZOJ 2707&colon; &lbrack;SDOI2012&rsqb;走迷宫 拓扑&plus;高斯消元&plus;期望概率dp&plus;Tarjan

    先Tarjan缩点 强连通分量里用高斯消元外面直接转移 注意删掉终点出边和拓扑 #include<cstdio> #include<cstring> #include<a ...

  2. 洛谷 P6030 - &lbrack;SDOI2012&rsqb;走迷宫(高斯消元&plus;SCC 缩点)

    题面传送门 之所以写个题解是因为题解区大部分题解的做法都有 bug(u1s1 周六上午在讨论区里连发两个 hack 的是我,由于我被禁言才让 ycx 代发的) 首先碰到这种期望题,我们套路地设 \(d ...

  3. BZOJ 2707&colon; &lbrack;SDOI2012&rsqb;走迷宫 &lbrack;高斯消元 scc缩点&rsqb;

    2707: [SDOI2012]走迷宫 题意:求s走到t期望步数,\(n \le 10^4\),保证\(|SCC| \le 100\) 求scc缩点,每个scc高斯消元,scc之间直接DP 注意每次清 ...

  4. BZOJ&period;2707&period;&lbrack;SDOI2012&rsqb;走迷宫&lpar;期望 Tarjan 高斯消元&rpar;

    题目链接 一个点到达终点的期望步数 \(E_i=\sum_{(i,j)\in G}\frac{E_j+1}{out[i]}\),\(out[i]\)为点\(i\)的出度. 那么对于一个DAG可以直接在 ...

  5. bzoj 2707 &lbrack;SDOI2012&rsqb;走迷宫(SCC&plus;高斯消元)

    Description Morenan被困在了一个迷宫里.迷宫可以视为N个点M条边的有向图,其中Morenan处于起点S,迷宫的终点设为T.可惜的是,Morenan非常的脑小,他只会从一个点出发随机沿 ...

  6. bzoj千题计划289:bzoj 2707&colon; &lbrack;SDOI2012&rsqb;走迷宫

    http://www.lydsy.com/JudgeOnline/problem.php?id=2707 dp[i] 表示从点i到终点的期望步数 dp[i]= Σ (dp[j]+1)/out[i] j ...

  7. BZOJ 3143 游走&lpar;贪心&plus;期望&plus;高斯消元&rpar;

    一个无向连通图,顶点从1编号到N,边从1编号到M. 小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分 ...

  8. BZOJ 3143 游走 &vert; 数学期望 高斯消元

    啊 我永远喜欢期望题 BZOJ 3143 游走 题意 有一个n个点m条边的无向联通图,每条边按1~m编号,从1号点出发,每次随机选择与当前点相连的一条边,走到这条边的另一个端点,一旦走到n号节点就停下 ...

  9. BZOJ&period;4820&period;&lbrack;SDOI2017&rsqb;硬币游戏&lpar;思路 高斯消元 哈希&sol;AC自动机&sol;KMP&rpar;

    BZOJ 洛谷 建出AC自动机,每个点向两个儿子连边,可以得到一张有向图.参照 [SDOI2012]走迷宫 可以得到一个\(Tarjan\)+高斯消元的\(O((nm)^3)\)的做法.(理论有\(6 ...

随机推荐

  1. Android程序进行混淆,在导出签名apk包时出错!

    今天终于完成了近一个月的App开发工作,对程序进行混淆导出签名apk包时,却出现了如下的错误: Proguard returned with error code 1. See console Not ...

  2. cas单点登录时报Invalid credentials

    CAS4后默认的密码验证不是简单的相同了.在配置文件deployerConfigContext.xml里可以找到, 默认是 Username:casuser Password:Mellon

  3. JAVA学习&lt&semi;四&gt&semi;

    一. 数组: Java 中操作数组只需要四个步骤: 1. 声明数组 语法:  数据类型[ ] 数组名: 或者   数据类型 数组名[ ]: 其中,数组名可以是任意合法的变量名. 2. 分配空间 简单地 ...

  4. 领域事件DomainEvents

    静态类DomainEvents: public static class DomainEvents { [ThreadStatic] private static List<Delegate&g ...

  5. UITableView详解&lpar;1&rpar;

    一,UITableView控件使用必备,红色部分是易错点和难点 首先创建一个项目,要使用UITableView就需要实现协议<UITableViewDataSource>,数据源协议主要完 ...

  6. Gradle使用手册(三):构建任务

    原文地址:http://tools.android.com/tech-docs/new-build-system/user-guide#TOC-Using-sourceCompatibility-1. ...

  7. C&plus;&plus; GUI Programming with Qt4 笔记 -- chap1

    1. Hello Qt #include <QApplication> #include <QLabel> int main(int argc, char *argv[]){ ...

  8. Unity NGUI的多分辨率适配

    参考链接:http://blog.csdn.net/mfc11/article/details/17681429,作者:CSDN mfc11 1.NGUI默认的适配方式: NGUI默认是适配方式是根据 ...

  9. kettle工具同步数据乱码-Linux下乱码问题二

    将写好的kettle工程部署到Linux下后,同步的数据都成了乱码,幸运的是数据库有备份. 下面就说一下,kettle工程如何同步两端编码格式都是utf8的数据库. 我们只需要更改kettle数据库连 ...

  10. Nginx 学习笔记(五)nginx-vod-module 模块

    nginx-vod-module 一.编译 ./configure \ --user=www \ --group=www \ --prefix=/usr/local/openresty \ --wit ...