[BZOJ3197/Luogu3296][SDOI2013]Assassin/刺客信条(树Hash,二分图)

发布于 2018-05-25  264 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3197/Luogu3296][SDOI2013]Assassin/刺客信条(树Hash,二分图)

Description

故事发生在1486 年的意大利,Ezio 原本只是一个文艺复兴时期的贵族,后来因为家族成员受到圣殿骑士的杀害,决心成为一名刺客。最终,凭借着他的努力和出众的天赋,成为了杰出的刺客大师,他不仅是个身手敏捷的武林高手,飞檐走壁擅长各种暗杀术。刺客组织在他的带领下,为被剥削的平民声张正义,赶跑了原本统治意大利的圣殿骑士首领-教皇亚历山大六世。在他的一生中,经历了无数次惊心动魄、扣人心弦的探险和刺杀。
曾经有一次,为了寻找Altair 留下的线索和装备,Ezio 在佛罗伦萨中的刺客墓穴进行探索。这个刺客墓穴中有许多密室,且任何两个密室之间只存在一条唯一的路径。这些密室里都有一个刺客标记,他可以启动或者关闭该刺客标记。为了打开储存着线索和装备的储藏室,Ezio 必须操作刺客标记来揭开古老的封印。要想解开这个封印,他需要通过改变某些刺客标记的启动情况,使得所有刺客标记与封印密码“看起来一样”。
在这里,“看起来一样”的定义是:存在一种“标记”密室与“密码”密室之间一一对应的关系,使得密室间的连接情况和启动情况相同(提示中有更详细解释)。幸运的是,在Ezio 来到刺客墓穴之前,在Da Vinci 的帮助下,Ezio 已经得知了打开储藏室所需要的密码。
而你的任务则是帮助Ezio 找出达成目标所需要最少的改动标记次数。

Tag

树Hash,二分图

解决思路

首先知道,一棵树如果重新编号后与自身同构,一定有重心不变,若重心有两个,则新建一个点连接两个重心,使得只有一个重心。
这样我们就可以确定以重心个点为根进行匹配。子树同构判断可以用树$$Hash$$来做。
预处理出任意一棵子树的$$Hash$$值后,设$$F[i][j]$$表示编号为$$i$$的点新编号为$$j$$后的最小代价,前提是$$i$$与$$j$$同构。那么,就需要把$$i$$和$$j$$的儿子进行匹配,由于保证儿子的值现在已经求出来了,所以对$$Hash$$值相同的连边,作二分图最小权匹配。这里采用费用流的形式实现。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3197/Luogu3296][SDOI2013]Assassin/刺客信条(树Hash,二分图)


HNCJ OIer