首页 > 其他分享 >牧师约翰最忙碌的一天

牧师约翰最忙碌的一天

时间:2024-05-30 18:32:57浏览次数:9  
标签:约翰 原图 忙碌 拓扑 SCC 当前 反图 节点 牧师

解释一下具体方案的选择

首先我们先抛开蓝书,来看看如果给了我们最终的图,我们如何选择,如下

于是我们所有的选择方法就是{①③,②④,①④,②③},总之来说就是镜像对称的不能同时选择

那么来看蓝书怎么搞的

首先是第一种方法,其实也就是在执行普通的拓扑排序而已,但是由于队列先进先出的性质,也就不会出现像下面的情况:我们选了①的第一个SCC,然后②的第一个SCC就不选了但是我们接下来却选择了②的第二个SCC而不是①的第二个SCC,导致①的第一个SCC与②的第二个SCC矛盾(这里的第一个第二个指的是拓扑序)

然后来看看第二种方法,其实也就是利用tarjan执行完之后,SCC的逆序是一个拓扑序,但我们需要证明原图中拓扑序的逆序列是反图的拓扑序

其实稍微想一下就知道,我们倒着执行原图的拓扑序,假设准备执行当前节点时,我们来想一下此时序列的意义

原图的拓扑序中,当前节点的后面的节点是在当前节点之后删除的,也就是说当前节点在原图的出边的终点一定排在原图拓扑序列中当前节点的后面,所以在反图上,我们倒着执行到当前节点的时候,当前节点在反图上入边的起点(也就是原图上出边的终点)一定都执行完了,所以当前节点在反图上的度数一定是\(0\),也就没有问题

然后还要注意到缩点之后连通块的SCC的编号是连续的,于是像这么写val[i] = c[i] > c[opp[i]];的正确性是可以保证的

标签:约翰,原图,忙碌,拓扑,SCC,当前,反图,节点,牧师
From: https://www.cnblogs.com/dingxingdi/p/18223016

相关文章

  • 【THM】开膛手约翰
    约翰是谁?开膛手约翰是目前最知名、最受欢迎和最通用的哈希破解工具之一。它结合了快速的破解速度和一系列非凡的兼容哈希类型。这个房间将假设没有以前的知识,因此在进入实际的哈希破解之前,我们必须首先介绍一些基本术语和概念。单词列表单词列表正如我们在第一个任务中解释的......
  • untiy小游戏——牧师与魔鬼_MVC架构
    牧师与魔鬼_MVC架构游戏介绍​牧师和魔鬼是一款益智游戏,您将在其中帮助牧师和魔鬼过河。河的一侧有3个祭司和3个魔鬼。他们都想去这条河的另一边,但只有一条船,这条船每次只能载两个人。而且必须有一个人将船从一侧驾驶到另一侧。您可以单击按钮来移动它们,然后单击移动按......
  • BZOJ 1022: [SHOI2008]小约翰的游戏John SG函数 Anti−SG
    1022:[SHOI2008]小约翰的游戏JohnTimeLimit: 1Sec  MemoryLimit: 162MBSubmit: 2667  Solved: 1701[Submit][Status][Discuss]Description小约翰经常和他的哥哥玩一个非常有趣的游戏:桌子上有n堆石子,小约翰和他的哥哥轮流取石子,每个人取的时候,可以随意选择一......
  • 漫画 | 为何你的忙碌换不来进步?你可能缺一个KISS模型
    在内卷严重的时代,让我们从思维开始,不断精进不断向上。101个思维模型系列小视频正陆续更新中,请戳:思维模型系列视频......
  • 精进:如何跳出疯狂的忙碌
    上周末开展了一次面向知识星球内部同学的直播分享,聊了很多质量保障体系建设的话题。有这样一个提问:跟领导汇报时要注重预期价值和明确的指标,但是这种价值在实践前没法量化,怎么办?这是一个很有意思的问题,我觉得也是体现一个人做事情思维方式的问题。这篇文章,聊聊我对于这个话题......
  • 工作的忙碌陷阱
    现在很多公司会出现996的工作模式,大家就会陷入一个“忙碌陷阱”。所谓忙碌陷阱就是:因为忙碌,所以没有时间去提升自己。因为没有去提升自己,所有很忙!只能停留在功能测试的级别我们没有办法转到自己能力之外的钱。如果你只会功能测试,你就只能看到所有人都是在做功能测试。你会自......
  • 约翰卡马克是何许人也?约翰卡马克和doom3
    卡马克完全可以做真正意义上的游戏之神啊,只不过欧美不像霓虹那样动不动喜欢吹个仙人但是卡马克干的事情,比一票游戏之神强多了1、手搓伪3D和真3D游戏图像引擎,引擎效果强大,吊锤当时的索尼世嘉任天堂2、引擎免费开源(真正意义上的造化众生)(直系最出名的就是CS系列)德军总部的源代码于......
  • dark and darker牧师怎么复活人 复活技能用不了_魔兽牧师复活技能叫什么
    darkanddarker,好欢乐的格斗游戏,每晚上班跟好朋友一同四人玩欢乐的批爆!假如你玩的是神父,刚开始的你很大会疑惑darkanddarker神父是并非重生老将,重生专业技能是并非用没法。darkanddarker神父是并非重生老将?可能将很多玩者玩神父重生的这个专业技能始终都是灰的用没法。原......
  • [化学微课] 约翰·道尔顿人物评价与科学精神分析
    约翰·道尔顿从兴趣出发,以兼具理论思维和实践研究的科学精神总结出气体分压定律,用科学实践证明了原子论和倍比定律,加速了19世纪新元素的发现、奠定了近代有机结构理论的基......
  • [化学微课]约翰·道尔顿生平介绍
    约翰·道尔顿(JohnDalton,1766年9月6日-1844年7月27日),英国物理学家、化学家。1.道尔顿简介约翰·道尔顿(JohnDalton,1766年9月6日-1844年7月27日),英国物理学家、化学......