P4186 [USACO18JAN]Cow at Large G

    • 248通过
    • 477提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 USACO 2018
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    题目描述

    最后,Bessie被迫去了一个远方的农场。这个农场包含N个谷仓(2 <= N <= 105)和N-1条连接两个谷仓的双向隧道,所以每两个谷仓之间都有唯一的路径。每个只与一条隧道相连的谷仓都是农场的出口。当早晨来临的时候,Bessie将在某个谷仓露面,然后试图到达一个出口。

    但当Bessie露面的时候,她的位置就会暴露。一些农民在那时将从不同的出口谷仓出发尝试抓住Bessie。农民和Bessie的移动速度相同(在每个单位时间内,每个农民都可以从一个谷仓移动到相邻的一个谷仓,同时Bessie也可以这么做)。农民们和Bessie总是知道对方在哪里。如果在任意时刻,某个农民和Bessie处于同一个谷仓或在穿过同一个隧道,农民就可以抓住Bessie。反过来,如果Bessie在农民们抓住她之前到达一个出口谷仓,Bessie就可以逃走。

    Bessie不确定她成功的机会,这取决于被雇佣的农民的数量。给定Bessie露面的谷仓K,帮助Bessie确定为了抓住她所需要的农民的最小数量。假定农民们会自己选择最佳的方案来安排他们出发的出口谷仓。

    输入格式

    输入的第一行包含N和K。接下来的N – 1行,每行有两个整数(在1~N范围内)描述连接两个谷仓的一条隧道。

    输出格式

    输出为了确保抓住Bessie所需的农民的最小数量。

    由 @Marser 提供翻译

    题目描述

    Cornered at last, Bessie has gone to ground in a remote farm. The farm consists of $N$ barns ($2 \leq N \leq 10^5$) and $N-1$ bidirectional tunnels between barns, so that there is a unique path between every pair of barns. Every barn which has only one tunnel is an exit. When morning comes, Bessie will surface at some barn and attempt to reach an exit.

    But the moment Bessie surfaces, the law will be able to pinpoint her location. Some farmers will then start at various exit barns, and attempt to catch Bessie. The farmers move at the same speed as Bessie (so in each time step, each farmer can move from one barn to an adjacent barn). The farmers know where Bessie is at all times, and Bessie knows where the farmers are at all times. The farmers catch Bessie if at any instant a farmer is in the same barn as Bessie, or crossing the same tunnel as Bessie. Conversely, Bessie escapes if she reaches an exit barn before any farms catch her.

    Bessie is unsure about her chances of success, which depends on the number of farmers that the law is able to deploy. Given that Bessie surfaces at barn $K$, help Bessie determine the minimum number of farmers who would be needed to catch Bessie, assuming that the farmers distribute themselves optimally among the exit barns.

    输入输出格式

    输入格式:

    The first line of the input contains $N$ and $K$. Each of the following $N-1$ lines specify two integers, each in the range $1 \ldots N$, describing a tunnel between two barns.

    输出格式:

    Please output the minimum number of farmers needed to ensure catching Bessie.

    输入输出样例

    输入样例#1: 复制
    7 1
    1 2
    1 3
    3 4
    3 5
    4 6
    5 7
    输出样例#1: 复制
    3
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。