P3296 [SDOI2013]刺客信条

    • 92通过
    • 262提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 哈希,HASH 费用流 2013 山东 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    故事发生在1486 年的意大利,Ezio 原本只是一个文艺复兴时期的贵族,后来因为家族成员受到圣殿骑士的杀害,决心成为一名刺客。最终,凭借着他的努力和出众的天赋,成为了杰出的刺客大师,他不仅是个身手敏捷的武林高手,飞檐走壁擅长各种暗杀术。刺客组织在他的带领下,为被剥削的平民声张正义,赶跑了原本统治意大利的圣殿骑士首领-教皇亚历山大六世。在他的一生中,经历了无数次惊心动魄、扣人心弦的探险和刺杀。

    曾经有一次,为了寻找Altair 留下的线索和装备,Ezio 在佛罗伦萨中的刺客墓穴进行探索。这个刺客墓穴中有许多密室,且任何两个密室之间只存在一条唯一的路径。这些密室里都有一个刺客标记,他可以启动或者关闭该刺客标记。为了打开储存着线索和装备的储藏室,Ezio 必须操作刺客标记来揭开古老的封印。要想解开这个封印,他需要通过改变某些刺客标记的启动情况,使得所有刺客标记与封印密码“看起来一样”。

    在这里,“看起来一样”的定义是:存在一种“标记”密室与“密码”密室之间一一对应的关系,使得密室间的连接情况和启动情况相同(提示中有更详细解释)。幸运的是,在Ezio 来到刺客墓穴之前,在Da Vinci 的帮助下,Ezio 已经得知了打开储藏室所需要的密码。

    而你的任务则是帮助Ezio 找出达成目标所需要最少的改动标记次数。

    输入输出格式

    输入格式:

    第一行给出一个整数n, 表示密室的个数,

    第二行至第 n 行, 每行绐出两个整数 a 和 b, 表示第 a 个密室和第 b 个密室之间存在一条通道.

    第 n+1行1 绐出 n 个整数1 分别表示当时每个密室的启动情况 {0表示关闭, 1表示启动).

    第 n+2 行7 给出 n 个整数, 分别表示密码中每个密室的启动情况.

    输出格式:

    输出只有一行,即输出最少改动标记次数

    输入输出样例

    输入样例#1: 复制
    4
    1 2
    2 3
    3 4
    0 0 1 1
    1 0 0 0
    输出样例#1: 复制
    1

    说明

    密室的编号是可以变的!将第三个密室关闭后,在当前标记和密码之间,存在1->4,2->3,3->2,4->1 的对应关系,重新编号后连接情况没有改变,且标记与密码对应。对于更一般的情况,存在一个1 到n 的置换P,使得对于任意密室之间的道路u-v,都一定有密码密室中的道路P(u)-P(v);如果不存在密室之间的道路u-v,则一定没有密码密室中的道路P(u)-P(v)。

    对于100%的数据,n<=700,且每个密室至多与11个密室相通

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。