← 返回题目列表

AtCoder · ijpc_animals2

A. 动物回归和森林更新

中文机器翻译题面 查看原题

曾经是茂密森林的土地被人类破坏了,生活在那里的动物也消失了。这是稍后的故事。

一直为所欲为的人类终于注意到了地球的尖叫声。人类对过去的行为感到遗憾,并开始开展保护环境和再生失去的森林的活动。

绿树正慢慢回到狐狸二郎和他的朋友们居住的地方。二郎和他的动物朋友们回到了他们熟悉的地方,想要再次玩耍。

新再生的森林里还有一个动物游乐场。动物们想要重建连接操场的道路,以便它们可以在操场之间来回走动,但由于它们还不习惯新的森林,所以他们决定让道路尽可能简单。

具体来说,我们希望从任何游乐场到任何其他游乐场都只有一条路径。这样,您就可以到达游乐场,而不必担心在新森林中迷路。创建这样一条路径的方法可能有很多种,所以让我们选择一种能够最小化路径总长度的方法。

你能帮助动物们在新森林里舒适地生活吗?

課題

首先,我们向仅由一个顶点组成的图添加顶点和边,最后增加顶点数量。 使其成为 N 。从一开始就存在的顶点有数字 0 已附加,并且顶点 在 i 之后立即添加的顶点有一个编号 i+1 可以添加 。

执行以下程序:

  • 具有以下参数的过程 构造(N、M、E):
    • N -- 顶点数。每个顶点按照添加顺序添加。0到N-1 它们的编号最大为。
    • M -- 可用边数。
    • E -- 表示有关可用边缘的信息的二维数组。 0 ≤ i < M 对于 ,边缘 i 是顶点 E[i][0] 和 E[i][1] 其长度为E[i][2]。0 ≤ E[i][0] < E[i][1] < N, 1 ≤ E[i][2] ≤ 1 000 000 000 可以假设。
    此程序答案(C) 必须调用输出为N-1 它们的编号最大为次。x次通话(1 ≤ x ≤ N-1),0以上x具有以下数字的顶点是x+1在不经过数目大于或等于顶点的顶点的情况下,允许以一种方式相互访问所需的边长之和中,最小C。然而,如果这样的边组合不存在,C = -1 让它成为。

例

図1
図 1

如图1所示 N = 5, M = 8,

E = 考虑 0 1 8
0 2 7
0 3 1
1 2 3
1 4 7
2 3 2
2 4 6
3 4 9

的情况。在这种情况下,构造满足答案输出为4次。以下是正确的 显示如何调用答案:

次数 (x) 致电
1 答案(8)
2 答案(10)
3 答案(6)
4 答案(12)

小課題

下面,在一次执行中 构造 调用参数 P 之和,即最终图的边数为 M 。

小課題 1 (16 点)

  • 1 ≤ N ≤ 1 000
  • 0 ≤ M ≤ 2 000

小課題 2 (24 点)

  • 1 ≤ N ≤ 5 000
  • 0 ≤ M ≤ 60 000

小課題 3 (59 点)

  • 1 ≤ N ≤ 20 000
  • 0 ≤ M ≤ 60 000

小課題 4 (1 点)

  • 1 ≤ N ≤ 100 000
  • 0 ≤ M ≤ 200 000

实施细节

制限

  • CPU时间限制:1.5秒
  • 内存限制:256 MB
    注意: 堆栈的大小没有固定限制。作为堆栈使用的内存包含在总内存使用量中。

接口 (API)

  • 实现文件夹:animals2/(原型: 动物2.zip)
  • 参赛者实现的文件:animals2.cpp
  • 提交文件接口:animals2.h
  • 评分程序示例:grader.cpp
  • 评分程序的示例输入:grader.in.1、grader.in.2、...
    注意:示例评分程序按以下格式读取输入。
    • 1 行目: N, M 用空格分隔。
    • 第2行到M+1: 对于 0 ≤ i < M 对于 ,i+2 行包含三个整数 E[i][0], E[i][1], E[i][2] 用空格分隔。
  • 评分器输入样本的预期输出:grader.expect.1、grader.expect.2、...
    注意:示例评分程序按以下格式写入输出。
    • 从第 1 行开始 N-1 它们的编号最大为 行目: 0 ≤ i < N-1 ,i+1 可以添加 行是 代表 构造是i 时间 包含调用 答案 时的返回值。