CodeForces - 123E Maze
http://codeforces.com/problemset/problem/123/E
题目翻译:(翻译来自: http://www.cogs.pw/cogs/problem/problem.php?pid=1734)
一个迷宫是一棵树(即一张无向图,其中任意两点之间仅有一条路径)。迷宫的起点和终点都按照某种概率随机选取。人们会在迷宫中用深度优先搜索的方法搜寻终点。如果有许多条可能的路径,会等概率地选取一条。考虑如下伪代码:
DFS(x)
if x == exit vertex then
finish search
flag[x] <- TRUE
random shuffle the vertices' order in V(x) // here all permutations have equal probability to be chosen
for i <- 1 to length[V] do
if flag[V[i]] = FALSE then
count++;
DFS(y);
count++;
V(x)是和x相邻的顶点列表。最初flag数组的值均为false。第一次DFS的参数是迷宫的入口节点。当搜索终止,变量count的值就是在迷宫中走的步数。
你的任务是计算在迷宫中从入口到出口,所走的期望步数。
题解:
首先一看知道题就知道应该去求每个点对答案的贡献
现在考虑如何求出这个贡献。
我们发现如果我们单独枚举一个点,那么这个点的情况一共有三种:
1.必定被经过
2.必定不被经过
3.不一定被经过
这样就不好统计了,所以我们先转换一下思维
怎样才能准确的找出经过的路径? 最直接的方法就是暴力枚举所有的起点和终点
这样路径就唯一确定了,直接在这个图中求一边期望,然后加权求和
可是 n <= 10^5,暴力肯定无法通过,但是有值得我们借鉴的思维
枚举端点
我们可以枚举终点,这样情况就分成了。。。还是三种:
1.起点就是终点,贡献为0,该情况可以忽略
2.起点在以终点为根的子树中
3.起点不在以终点为根的子树中
对于第二种情况,我们可以直接计算贡献,即(子树的节点数目*子树中有一个点作为入口的概率)
对于第三种情况,我们也可以直接计算的,即(除去子树后树的节点数目*除去子树后树中存在入口的概率)
为什么能这么计算呢?
我们考虑一下,如果根的某一个儿子是入口,那么贡献应为0.5*siz[v]*2
我们发现,如果一条路径经过n个点两次后到达出口,那么对答案的贡献即为(n<<1)
我们可以这么想,把题目中给的伪代码改动一下,那么每次到达一个点++count,退出一个点++count
最后再--count,这样就是这条路径对答案的贡献。
所以,我们直接刨去到达终点时对答案做出的贡献,那么就可以得到刚才的式子了
我们考虑进行推广,发现所有的点都满足这个式子
所以我们可以直接对若干个点直接加和,那么就是上面提到的计算方式了
O(n)
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=*x+ch-'',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
const int maxn = ;
struct Edge{
int to,next;
}G[maxn<<];
int head[maxn],cnt;
void add(int u,int v){
G[++cnt].to = v;
G[cnt].next = head[u];
head[u] = cnt;
}
int siz[maxn],ex[maxn],en[maxn];
int fa[maxn],n;
ll sn=,sx=,ans = ;
#define v G[i].to
void dfs(int u){
siz[u] = ;
for(int i = head[u];i;i=G[i].next){
if(v == fa[u]) continue;
fa[v] = u;
dfs(v);
siz[u] += siz[v];
en[u] += en[v];
ans += 1LL*ex[u]*en[v]*siz[v];
}ans += 1LL*ex[u]*(sn - en[u])*(n - siz[u]);
}
#undef v
int main(){
read(n);
for(int i=,u,v;i<n;++i){
read(u);read(v);
add(u,v);add(v,u);
}
for(int i=;i<=n;++i){
read(en[i]),read(ex[i]);
sn += en[i];sx += ex[i];
}dfs();
printf("%.60lf\n",(double)ans/(1.0*sn*sx) );
getchar();getchar();
return ;
}
最新文章
- .添加索引和类型,同时设定edgengram分词和charsplit分词
- IDE编辑器编码配置
- guava之Joiner 和 Splitter
- 前端资源多个产品整站一键打包&;包版本管理(三)—— gulp分流
- 利用FTP将Linux文件备份到Windows
- TCP/IP之三次握手、四次挥手
- 技术方案:在外部网址调试本地js(基于fiddler)
- linux命令11
- 02_JNI中Java代码调用C代码,Android中使用log库打印日志,javah命令的使用,Android.mk文件的编写,交叉编译
- golang 安装tensorflow
- hr相关的
- 海量日志采集Flume(HA)
- MySQL误删数据
- 20155208徐子涵 2016-2017-2 《Java程序设计》第4周学习总结
- php大数除法保留精度问题
- jQuery中的观察者模式(Observer Pattern)
- docker get 到的命令 (持续更新)
- hihoCoder 1014 Trie树 (Trie)
- 焦作网络赛E-JiuYuanWantstoEat【树链剖分】【线段树】
- 高可用Kubernetes集群-7. 部署kube-controller-manager