P4294 [WC2008]游览计划

    • 336通过
    • 711提交
  • 题目提供者 Imagine
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 最短路 状态压缩,状压 进制 WC/CTSC/集训队 2008 Special Judge
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    从未来过绍兴的小D有幸参加了Winter Camp 2008,他被这座历史名城的秀丽风景所吸引,强烈要求游览绍兴及其周边的所有景点。

    主办者将绍兴划分为N行M列(N×M)个分块,如下图(8×8):

    景点含于方块内,且一个方块至多有一个景点。无景点的方块视为路。

    为了保证安全与便利,主办方依据路况和治安状况,在非景点的一些方块内安排不同数量的志愿者;在景点内聘请导游(导游不是志愿者)。在选择旅游方案时,保证任意两个景点之间,存在一条路径,在这条路径所经过的每一个方块都有志愿者或者该方块为景点。既能满足选手们游览的需要,又能够让志愿者的总数最少。

    例如,在上面的例子中,在每个没有景点的方块中填入一个数字,表示控制该方块最少需要的志愿者数目:

    图中用深色标出的方块区域就是一种可行的志愿者安排方案,一共需要20名志愿者。由图可见,两个相邻的景点是直接(有景点内的路)连通的(如沈园和八字桥)。

    现在,希望你能够帮助主办方找到一种最好的安排方案。

    输入输出格式

    输入格式:

    第一行有两个整数,N和M,描述方块的数目。

    接下来N行,每行有M个非负整数,如果该整数为0,则该方块为一个景点;

    否则表示控制该方块至少需要的志愿者数目。相邻的整数用(若干个)空格隔开,

    行首行末也可能有多余的空格。

    输出格式:

    由N+1行组成。第一行为一个整数,表示你所给出的方案中安排的志愿者总数目。

    接下来N行,每行M个字符,描述方案中相应方块的情况:

    '_'(下划线)表示该方块没有安排志愿者;

    'o'(小写英文字母o)表示该方块安排了志愿者;

    'x'(小写英文字母x)表示该方块是一个景点;

    注:请注意输出格式要求,如果缺少某一行或者某一行的字符数目和要求不一致(任何一行中,多余的空格都不允许出现),都可能导致该测试点不得分。

    输入输出样例

    输入样例#1: 复制
    4 4
    0 1 1 0
    2 5 5 1
    1 5 5 1
    0 1 1 0
    输出样例#1: 复制
    6
    xoox
    ___o
    ___o
    xoox

    说明

    所有的 10 组数据中 N, M ,以及景点数 K 的范围规定如下

    输入文件中的所有整数均不小于 0 且不超过 2^16

    感谢@panda_2134 提供Special Judge

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