当前位置: 首页 > news >正文

[NOI2012]迷失游乐园

传送门

Description

基环树上随机选择一个点做起点,等概率向其相邻的节点移动,保证每个点只经过不超过\(1\)

求期望的最大游走距离

Solution

假设环处在最上面的位置

\(down_x\)表示向下走的期望距离,\(up_x\)表示向上走的期望距离

那么如果是树的话
\[ down_x=\sum \frac{w(E<x,son_i>)+down_{son_i}}{degree_x-1} \]

\[ up_x=\frac{up_{fa}+down_{fa}*(degree_{fa}-1-w(E<x,fa>)-down[x])}{degree_{fa}-1} \]

对于环,其实求\(down_x\)的部分是不会变得

考虑如果求得了环上每个点的\(up\),那么外向树上的点\(up\)值可以类似树的方式求得

对于环上一个点:

首先它有可能往逆时针或顺时针走,概率相等

对于一个方向,它有可能顺着环走到一个点后开始向下走,进入该点的子树

求出到这个点的概率,再乘上它的\(down\)


Code 

#include<bits/stdc++.h>
#define reg register
#define db double
inline int read()
{
    reg int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
const int MN=1e5+5;
int N,M,d[MN],son[MN];
struct edge{int to,w,nex;}e[MN<<1];
int hr[MN],en;
void ins(int x,int y,int w)
{
    e[++en]=(edge){y,w,hr[x]};hr[x]=en;
    e[++en]=(edge){x,w,hr[y]};hr[y]=en;
}
db down[MN],up[MN],ans;
bool vis[MN],inr[MN],flag;
int st[MN],last[MN],tp,cir[MN],num;
void tj(int x,int f)
{
    if(flag) return;
    vis[x]=true;st[tp++]=x;reg int i;
    for(i=hr[x];i;i=e[i].nex) if(f^e[i].to&&!flag)
    if(!vis[e[i].to]) last[e[i].to]=e[i].w,tj(e[i].to,x);
    else
    {
        last[e[i].to]=e[i].w;
        for(;st[tp]!=e[i].to;--tp)
            inr[cir[num++]=st[tp-1]]=true;
        flag=true;
        return;
    }
    if(st[tp-1]==x) --tp;
}
void dfs1(int x,int f)
{//down
    reg int i;
    for(i=hr[x];i;i=e[i].nex)if((f^e[i].to)&&!inr[e[i].to])
        ++son[x],dfs1(e[i].to,x),down[x]+=e[i].w+down[e[i].to];
    if(son[x])down[x]/=(db)son[x];
}
int Rt;
void dfs2(int x,int f,int len=0)
{//up
    reg int i;
    if(x!=Rt) up[x]=len+(db)(up[f]*(d[f]-son[f])+down[f]*son[f]-len-down[x])/(db)(d[f]>1?d[f]-1:1);
    for(i=hr[x];i;i=e[i].nex)if((f^e[i].to)&&!inr[e[i].to]) dfs2(e[i].to,x,e[i].w);
}
int main()
{
    N=read();M=read();reg int i,j,x,y;
    for(i=1;i<=M;++i) x=read(),y=read(),ins(x,y,read()),++d[x],++d[y];
    if(M==N-1) dfs1(1,0),dfs2(Rt=1,0);
    else
    {
        tj(1,0);for(i=0;i<num;++i) dfs1(cir[i],0);
        for(i=0;i<num;++i)
        {
            db p1=.5,p2=.5,s1=(db)last[cir[i]],s2=0.;
            for(j=1;j<num;++j)
            {
                x=(i+j)%num;y=(i-j+num)%num;
                s2+=(db)last[cir[y]];
                if(j==num-1)
                {
                    up[cir[i]]+=p1*(s1+down[cir[x]]);
                    up[cir[i]]+=p2*(s2+down[cir[y]]);
                    break;
                }
                up[cir[i]]+=p1*((db)son[cir[x]]/(db)(d[cir[x]]-1))*(s1+down[cir[x]]);
                p1*=1./(d[cir[x]]-1);
                up[cir[i]]+=p2*((db)son[cir[y]]/(db)(d[cir[y]]-1))*(s2+down[cir[y]]);
                p2*=1./(d[cir[y]]-1);
                s1+=(db)last[cir[x]];
            }
        }
        for(i=0;i<num;++i) dfs2(Rt=cir[i],0);
    }
    for(i=1;i<=N;++i)
    ans+=(up[i]*(db)(d[i]-son[i])+down[i]*(db)son[i])/(db)d[i];
    ans/=(db)N;
    printf("%.5lf\n",ans);
    return 0;
}



Blog来自PaperCloud,未经允许,请勿转载,TKS!

转载于:https://www.cnblogs.com/PaperCloud/p/10657032.html

相关文章:

  • WinPhone学习笔记(四)——磁贴
  • 第六周作业
  • NLPIR(北理工张华平版中文分词系统)的SDK(C++)调用方法
  • jqGrid 基础
  • 利用KMP算法解决串的模式匹配问题(c++) -- 数据结构
  • 高级排序算法之归并排序
  • C#winform程序安装时自动卸载新版本覆盖旧版本
  • 第二次实验报告
  • 数据库原理 知识点总结
  • Express初识
  • MyBatis Dynamic SQL 1.1.1 发布,生成动态 SQL 的框架
  • 21个值得收藏的Javascript技巧
  • 43. Multiply Strings字符串相乘
  • displayport-2
  • 他山之石——运维平台哪家强?
  • [nginx文档翻译系列] 控制nginx
  • AWS实战 - 利用IAM对S3做访问控制
  • CSS3 聊天气泡框以及 inherit、currentColor 关键字
  • FastReport在线报表设计器工作原理
  • javascript数组去重/查找/插入/删除
  • js中forEach回调同异步问题
  • Python代码面试必读 - Data Structures and Algorithms in Python
  • Vue2.0 实现互斥
  • vue--为什么data属性必须是一个函数
  • zookeeper系列(七)实战分布式命名服务
  • 动态魔术使用DBMS_SQL
  • 看域名解析域名安全对SEO的影响
  • 那些被忽略的 JavaScript 数组方法细节
  • 如何学习JavaEE,项目又该如何做?
  • 三栏布局总结
  • 适配iPhoneX、iPhoneXs、iPhoneXs Max、iPhoneXr 屏幕尺寸及安全区域
  • 小程序、APP Store 需要的 SSL 证书是个什么东西?
  • 赢得Docker挑战最佳实践
  • 再谈express与koa的对比
  • 自动记录MySQL慢查询快照脚本
  • [地铁译]使用SSD缓存应用数据——Moneta项目: 低成本优化的下一代EVCache ...
  • 阿里云ACE认证学习知识点梳理
  • 阿里云服务器购买完整流程
  • ​2020 年大前端技术趋势解读
  • ​520就是要宠粉,你的心头书我买单
  • ###C语言程序设计-----C语言学习(6)#
  • #pragma multi_compile #pragma shader_feature
  • #pragma pack(1)
  • (android 地图实战开发)3 在地图上显示当前位置和自定义银行位置
  • (javascript)再说document.body.scrollTop的使用问题
  • (切换多语言)vantUI+vue-i18n进行国际化配置及新增没有的语言包
  • .net 托管代码与非托管代码
  • .NET 中 GetHashCode 的哈希值有多大概率会相同(哈希碰撞)
  • .Net程序猿乐Android发展---(10)框架布局FrameLayout
  • .NET牛人应该知道些什么(2):中级.NET开发人员
  • .NET与 java通用的3DES加密解密方法
  • @ModelAttribute 注解
  • [1525]字符统计2 (哈希)SDUT
  • [AI]文心一言爆火的同时,ChatGPT带来了这么多的开源项目你了解吗
  • [Android View] 可绘制形状 (Shape Xml)