首页 > 其他分享 >P9534 [YsOI2023] 广度优先遍历

P9534 [YsOI2023] 广度优先遍历

时间:2023-08-14 09:45:07浏览次数:41  
标签:对于 DAG ba YsOI2023 那么 父亲 遍历 P9534 顺序

好题。

首先考虑到对于任意的边的输入顺序,分层图是不会变的,即所有点到根的最短距离不变。

那么分为两种边,分别为不同层的边相连,相同层的边相连。

显然第二种边是无用的,我们将其放到最后输出即可。

由于下层的决策会影响上层的决策而且不同层之间的边的顺序不会影响答案,所以我们按分层图从大到小处理。

不妨设当前层为 $t$,那么上一层为 $t-1$,对于连接不同层的边,层数大的儿子,小的为父亲,节点 $x$ 的真父亲是 $ba_x$,$t-1$ 到 $t$ 的边的顺序只有两种因素决定:$t$ 层的点的相对顺序,以及 $t$ 层的点 $x$ 所有父亲的相对关系。

对于第一种情况,显然对于每个点都要被真父亲选走,所以 $ba_x$ 要在其他父亲之前。

对于第二种情况,一种暴力的做法是枚举 $t$ 层任意两点 $x,y$,如果 $x$ 要在 $y$ 之前,那么 $ba_x$ 也一定要在 $ba_y$之前。

由于答案一定存在,那么每一层的相对关系一定由多个 $DAG$ 组成,我们对每个点赋值 $p$,那么如果 $x$ 在 $y$ 之前,那么 $p_x$ 一定比 $p_y$ 小。

这里存在一个问题,有可能对于两个不同 $DAG$ 的点,$p$ 值也会存在一个相对关系,但在原图中这是没有的,所以我们要再建立并查集,维护每个 $DAG$ 里面的节点。

那么我们对同层的边排序的时候,先考虑并查集祖先,然后考虑父亲的权值,再考虑儿子的权值。

可是这个是 $\sum d^2 log{d}$ 的算法,$d$ 为每层的点数,不排除能过 $1e5$

标签:对于,DAG,ba,YsOI2023,那么,父亲,遍历,P9534,顺序
From: https://www.cnblogs.com/Hanghang007/p/17627810.html

相关文章

  • import.meta.globEager('./src/components/**/*.vue'); 遍历文件
    main.jsconstimportAll=(modules)=>{Object.keys(modules).forEach((key)=>{constcomponent=key.replace('/src/','@/').replace('.vue','');constcomponentName=key.split('/').slice......
  • 二叉树的层序遍历
    intfindBottomLeftValue(TreeNode*root){queue<TreeNode*>qu;if(root!=nullptr)qu.push(root);intsize=0;intresult=0;while(!qu.empty()){TreeNode*temp;size=qu.size();......
  • 代码随想录算法训练营第十五天| 层序遍历 10 ,226.翻转二叉树 101.对称二叉树 2
     层序遍历   卡哥建议:看完本篇可以一口气刷十道题,试一试, 层序遍历并不难,大家可以很快刷了十道题。  题目链接/文章讲解/视频讲解:https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html  做题思......
  • JavaScript访问者模式:优雅地遍历对象
    JavaScript访问者模式JavaScript中的访问者模式是一种优雅的设计模式,它可以帮助我们遍历对象并执行特定操作。在本文中,我们将介绍访问者模式的概念、实现方式以及一个简单的示例。什么是访问者模式?访问者模式是一种行为型设计模式,它允许我们在不改变对象结构的情况下,定义新的操......
  • java中table遍历td js遍历table中的tr
    一、获取每一个tr1、通过table的id获取id="tables"获取第一行tr,索引从0开始,用eq(),方法里面的索引可以手动更换,如第二行就是1,也可以循环tr,eq里面就是循环变量$("#tablestr").eq(0);//遍历每一行for(vari=0;i<$("#tablestr").length;i++){ $("#tablestr").eq(i);......
  • 代码随想录算法训练营第十四天| 理论基础 递归遍历 迭代遍历
     理论基础    卡哥建议:需要了解 二叉树的种类,存储方式,遍历方式 以及二叉树的定义   文章讲解:https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html   补充的知识点:   名词的概念看卡哥文章。二叉树......
  • Java遍历集合(List,Map)
    遍历ListpublicvoiditeratorList(){List<String>list=newArrayList<>();list.add("a");list.add("b");//方法1使用iterator遍历Iterator<String>iterator=list.iterator();w......
  • 二叉树后序遍历非递归遍历实现图解
    二叉树的后序遍历输入:{1,#,2,3}返回值:[3,2,1]输入:{1}返回值:[1]代码实现publicint[]postorderTraversal(TreeNoderoot){TreeNodecur=root;List<Integer>list=newArrayList<>();Deque<TreeNode>stack=newArrayDeq......
  • python 文件夹遍历三种方法
    os.listdir(path),返回path目录下的文件夹和文件,但不包含子文件夹里的文件夹和文件递归遍历所有文件importosdefrecursive_listdir(path):files=os.listdir(path)forfileinfiles:file_path=os.path.join(path,file)ifos.path.isfile......
  • 144. 二叉树的前序遍历
    给你二叉树的根节点 root ,返回它节点值的 前序 遍历。示例1:输入:root=[1,null,2,3]输出:[1,2,3]示例2:输入:root=[]输出:[]示例3:输入:root=[1]输出:[1]示例4:输入:root=[1,2]输出:[1,2]classSolution:defpreorderTraversal(self,root:Optional[TreeNode])->Li......