全国信息学奥林匹克联赛（NOIP2012）复赛 提高组 day2 第 3页 共 4页 【输入】 输入文件为 classroom.in。 第一行包含两个正整数n, m，表示天数和订单的数量。 第二行包含n个正整数，其中第i个数为ri，表示第i天可用于租借的教室数量。 接下来有m行，每行包含三个正整数dj, sj, tj，表示租借的数量，租借开始、结束分别在 第几天。 每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1开始的整数编号。 【输出】 输出文件为 classroom.out。 如果所有订单均可满足，则输出只有一行，包含一个整数0。否则（订单无法完全满足） 输出两行，第一行输出一个负整数-1，第二行输出需要修改订单的申请人编号。 【输入输出样例】 classroom.in classroom.out 4 3 2 5 4 3 2 1 3 3 2 4 4 2 4 -1 2 【输入输出样例说明】 第 1份订单满足后，4天剩余的教室数分别为 0，3，2，3。第 2份订单要求第 2天到 第 4天每天提供 3个教室，而第 3天剩余的教室数为 2，因此无法满足。分配停止，通知第 2个申请人修改订单。 【数据范围】 对于 10%的数据，有1 ≤ n, m ≤ 10； 对于 30%的数据，有1 ≤ n, m ≤ 1000； 对于 70%的数据，有1 ≤ n, m ≤ 105； 对于 100%的数据，有1 ≤ n, m ≤ 106, 0 ≤ ri, dj ≤ 109, 1 ≤ sj ≤ tj ≤ n。 3．疫情控制 （blockade.cpp/c/pas） 【问题描述】 H国有 n个城市， 这n个城市用 n-1条双向道路相互连通构成一棵树，1号城市是首都， 也是树中的根节点。 H国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境 城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境 城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注意的是， 首都是不能建立检查点的。 现在，在 H国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军 全国信息学奥林匹克联赛（NOIP2012）复赛 提高组 day2 第 4页 共 4页 队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在 一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等 于道路的长度（单位：小时） 。 请问最少需要多少个小时才能控制疫情。注意：不同的军队可以同时移动。 【输入】 输入文件名为blockade.in。 第一行一个整数 n，表示城市个数。 接下来的 n-1行，每行 3个整数，u、v、w，每两个整数之间用一个空格隔开，表示从 城市 u到城市 v有一条长为 w的道路。数据保证输入的是一棵树，且根节点编号为 1。 接下来一行一个整数 m，表示军队个数。 接下来一行 m个整数，每两个整数之间用一个空格隔开，分别表示这 m个军队所驻扎 的城市的编号。 【输出】 输出文件为blockade.out。 共一行，包含一个整数，表示控制疫情所需要的最少时间。如果无法控制疫情则输出-1。 【输入输出样例】
blockade.in blockade.out 4 1 2 1 1 3 2 3 4 3 2 2 2 3 【输入输出样例说明】 第一支军队在 2号点设立检查点，第二支军队从 2号点移动到 3号点设立检查点，所需 时间为 3个小时。 【数据范围】 保证军队不会驻扎在首都。 对于 20%的数据，2≤ n≤ 10； 对于 40%的数据，2 ≤n≤50，0<w <105； 对于 60%的数据，2 ≤ n≤1000，0<w <106； 对于 80%的数据，2 ≤ n≤10,000； 对于 100%的数据，2≤m≤n≤50,000，0<w <109。