P4268 [USACO18FEB]Directory Traversal

    • 90通过
    • 164提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 搜索 线性递推,递推式 递推 USACO 2018
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    奶牛Bessie令人惊讶地精通计算机。她在牛棚的电脑里用一组文件夹储存了她所有珍贵的文件,比如:

    bessie/
      folder1/
        file1
        folder2/
          file2
      folder3/
        file3
      file4

    只有一个“顶层”的文件夹,叫做bessie。

    Bessie可以浏览任何一个她想要访问的文件夹。从一个给定的文件夹,每一个文件都可以通过一个“相对路径”被引用。在一个相对路径中,符号“..”指的是上级目录。如果Bessie在folder2中,她可以按下列路径引用这四个文件:

    ../file1
    file2
    ../../folder3/file3
    ../../file4

    Bessie想要选择一个文件夹,使得从该文件夹出发,对所有文件的相对路径的长度之和最小。

    输入格式(文件名:dirtraverse.in): 第一行包含一个整数N($2 \leq N \leq 100,000$),为所有文件和文件夹的总数量。为了便于输入,每个对象(文件或文件夹)被赋予一个唯一的1至$N$之间的ID,其中ID 1指的是顶层文件夹。 接下来有$N$行。每行的第一项是一个文件或是文件夹的名称。名称仅包含小写字母a-z和数字0-9,长度至多为16个字符。名称之后是一个整数$m$。如果$m$为0,则该对象是一个文件。如果$m > 0$,则该对象是一个文件夹,并且该文件夹下共有$m$个文件或文件夹。在$m$之后有$m$个整数,为该文件夹下的对象的ID。

    输出格式(文件名:dirtraverse.out): 输出所有文件的相对路径的长度之和的最小值。注意这个值可能超过32位整数的表示范围。

    题目描述

    Bessie the cow is surprisingly computer savvy. On her computer in the barn, she stores all of her precious files in a collection of directories; for example:

    bessie/
      folder1/
        file1
        folder2/
          file2
      folder3/
        file3
      file4

    There is a single "top level" directory, called bessie.

    Bessie can navigate to be inside any directory she wants. From a given directory, any file can be referenced by a "relative path". In a relative path, the symbol ".." refers to the parent directory. If Bessie were in folder2, she could refer to the four files as follows:

    ../file1
    file2
    ../../folder3/file3
    ../../file4

    Bessie would like to choose a directory from which the sum of the lengths of the relative paths to all the files is minimized.

    输入输出格式

    输入格式:

    The first line contains an integer N ($2 \leq N \leq 100,000$), giving the total number of files and directories. For the purposes of input, each object (file or directory) is assigned a unique integer ID between 1 and $N$, where ID 1 refers to the top level directory. Next, there will be $N$ lines. Each line starts with the name of a file or directory. The name will have only lower case characters a-z and digits 0-9, and will be at most 16 characters long. Following the name is an integer, $m$. If $m$ is 0, then this entity is a file. If $m > 0$, then this entity is a directory, and it has a total of $m$ files or directories inside it. Following $m$ there will be $m$ integers giving the IDs of the entities in this directory.

    输出格式:

    Output the minimal possible total length of all relative paths to files. Note that this value may be too large to fit into a 32-bit integer.

    输入输出样例

    输入样例#1: 复制
    8
    bessie 3 2 6 8
    folder1 2 3 4
    file1 0
    folder2 1 5
    file2 0
    folder3 1 7
    file3 0
    file4 0
    输出样例#1: 复制
    42

    说明

    This input describes the example directory structure given above.

    The best solution is to be in folder1. From this directory, the relative paths are:

    file1
    folder2/file2
    ../folder3/file3
    ../file4

    Problem credits: Mark Gordon

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