数据范围太大不能直接高斯消元, tarjan缩点然后按拓扑逆序对每个强连通分量高斯消元就可以了.
E(u) = 1 + Σ E(v) / degree(u)
对拍时发现网上2个程序的INF判断和我不一样(他们2个的INF判断也不一样).....然而都A掉了....我觉得应该是他们写错了,我的做法应该没错的(正反2遍dfs,GDOI2015day1t1大冒险)(求打脸
------------------------------------------------------------------------
------------------------------------------------------------------------
2707: [SDOI2012]走迷宫
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 372 Solved: 149
[Submit][Status][Discuss]
Description
Input
Output
测试点
|
N
|
M
|
Hint
|
[1, 6]
|
<=10
|
<=100
|
|
[7, 12]
|
<=200
|
<=10000
|
|
[13, 20]
|
<=10000
|
<=1000000
|
保证强连通分量的大小不超过100
|
Sample Input
Sample Output
HINT
Source
BZOJ 2707: [SDOI2012]走迷宫( tarjan + 高斯消元 )的更多相关文章
-
BZOJ 2707: [SDOI2012]走迷宫 拓扑+高斯消元+期望概率dp+Tarjan
先Tarjan缩点 强连通分量里用高斯消元外面直接转移 注意删掉终点出边和拓扑 #include<cstdio> #include<cstring> #include<a ...
-
洛谷 P6030 - [SDOI2012]走迷宫(高斯消元+SCC 缩点)
题面传送门 之所以写个题解是因为题解区大部分题解的做法都有 bug(u1s1 周六上午在讨论区里连发两个 hack 的是我,由于我被禁言才让 ycx 代发的) 首先碰到这种期望题,我们套路地设 \(d ...
-
BZOJ 2707: [SDOI2012]走迷宫 [高斯消元 scc缩点]
2707: [SDOI2012]走迷宫 题意:求s走到t期望步数,\(n \le 10^4\),保证\(|SCC| \le 100\) 求scc缩点,每个scc高斯消元,scc之间直接DP 注意每次清 ...
-
BZOJ.2707.[SDOI2012]走迷宫(期望 Tarjan 高斯消元)
题目链接 一个点到达终点的期望步数 \(E_i=\sum_{(i,j)\in G}\frac{E_j+1}{out[i]}\),\(out[i]\)为点\(i\)的出度. 那么对于一个DAG可以直接在 ...
-
bzoj 2707 [SDOI2012]走迷宫(SCC+高斯消元)
Description Morenan被困在了一个迷宫里.迷宫可以视为N个点M条边的有向图,其中Morenan处于起点S,迷宫的终点设为T.可惜的是,Morenan非常的脑小,他只会从一个点出发随机沿 ...
-
bzoj千题计划289:bzoj 2707: [SDOI2012]走迷宫
http://www.lydsy.com/JudgeOnline/problem.php?id=2707 dp[i] 表示从点i到终点的期望步数 dp[i]= Σ (dp[j]+1)/out[i] j ...
-
BZOJ 3143 游走(贪心+期望+高斯消元)
一个无向连通图,顶点从1编号到N,边从1编号到M. 小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分 ...
-
BZOJ 3143 游走 | 数学期望 高斯消元
啊 我永远喜欢期望题 BZOJ 3143 游走 题意 有一个n个点m条边的无向联通图,每条边按1~m编号,从1号点出发,每次随机选择与当前点相连的一条边,走到这条边的另一个端点,一旦走到n号节点就停下 ...
-
BZOJ.4820.[SDOI2017]硬币游戏(思路 高斯消元 哈希/AC自动机/KMP)
BZOJ 洛谷 建出AC自动机,每个点向两个儿子连边,可以得到一张有向图.参照 [SDOI2012]走迷宫 可以得到一个\(Tarjan\)+高斯消元的\(O((nm)^3)\)的做法.(理论有\(6 ...
随机推荐
-
Android程序进行混淆,在导出签名apk包时出错!
今天终于完成了近一个月的App开发工作,对程序进行混淆导出签名apk包时,却出现了如下的错误: Proguard returned with error code 1. See console Not ...
-
cas单点登录时报Invalid credentials
CAS4后默认的密码验证不是简单的相同了.在配置文件deployerConfigContext.xml里可以找到, 默认是 Username:casuser Password:Mellon
-
JAVA学习<;四>;
一. 数组: Java 中操作数组只需要四个步骤: 1. 声明数组 语法: 数据类型[ ] 数组名: 或者 数据类型 数组名[ ]: 其中,数组名可以是任意合法的变量名. 2. 分配空间 简单地 ...
-
领域事件DomainEvents
静态类DomainEvents: public static class DomainEvents { [ThreadStatic] private static List<Delegate&g ...
-
UITableView详解(1)
一,UITableView控件使用必备,红色部分是易错点和难点 首先创建一个项目,要使用UITableView就需要实现协议<UITableViewDataSource>,数据源协议主要完 ...
-
Gradle使用手册(三):构建任务
原文地址:http://tools.android.com/tech-docs/new-build-system/user-guide#TOC-Using-sourceCompatibility-1. ...
-
C++ GUI Programming with Qt4 笔记 -- chap1
1. Hello Qt #include <QApplication> #include <QLabel> int main(int argc, char *argv[]){ ...
-
Unity NGUI的多分辨率适配
参考链接:http://blog.csdn.net/mfc11/article/details/17681429,作者:CSDN mfc11 1.NGUI默认的适配方式: NGUI默认是适配方式是根据 ...
-
kettle工具同步数据乱码-Linux下乱码问题二
将写好的kettle工程部署到Linux下后,同步的数据都成了乱码,幸运的是数据库有备份. 下面就说一下,kettle工程如何同步两端编码格式都是utf8的数据库. 我们只需要更改kettle数据库连 ...
-
Nginx 学习笔记(五)nginx-vod-module 模块
nginx-vod-module 一.编译 ./configure \ --user=www \ --group=www \ --prefix=/usr/local/openresty \ --wit ...