没有合适的资源?快使用搜索试试~ 我知道了~
2023“钉耙编程”中国大学生算法设计超级联赛(1)-题目集.pdf
需积分: 5 0 下载量 105 浏览量
2023-07-27
20:59:01
上传
评论
收藏 222KB PDF 举报
温馨提示
试读
14页
2023“钉耙编程”中国大学生算法设计超级联赛(1)-题目集
资源推荐
资源详情
资源评论
Super League of Chinese College Students Algorithm Design 2023 1
China, July, 18, 2018
Problem A. Hide-And-Seek Game
Input file: standard input
Output file: standard output
Time limit: 5 seconds
Memory limit: 128 megabytes
During the summer vacation, Serenade and Rhapsody are playing hide-and-seek in a park structured as
a tree. Each edge of the tree has a weight of 1. Serenade keeps running back and forth between S
a
and T
a
(S
a
6= T
a
), while Rhapsody runs back and forth between S
b
and T
b
(S
b
6= T
b
). However, Aria doesn’t want
to run around with them and only wants to know the earliest location where Serenade and Rhapsody
will meet. Please output the identification number of this location.If they will never meet, output -1.
To be more specific, Serenade starts from S
a
and moves one edge towards T
a
each time. Once reaching
T
a
, Serenade then moves one edge towards S
a
each time. After reaching S
a
, Serenade moves one edge
towards T
a
each time, and so on. Rhapsody follows a similar pattern of movement.
Note that this park is quite mysterious, so Ser enade and Rhapsody will not meet on an edge (you
can assume that they will choose different paths to traverse the same edge).
Input
The input consists of multiple test cases. The first line contains a single integer t(1 ≤ t ≤ 500) — the
number of test cases. Description of the test cases follows.
The first line of each test case contains two integers n and m (2 ≤ n, m ≤ 3 · 10
3
) — the number of the
vertices in the given tree and the number of questions.
Each of the next n − 1 lines contains two integers u and v (1 ≤ u, v ≤ n, u 6= v) meaning that there is an
edge between vertices u and v in the tree.
Each of the next m lines contains four integers S
a
, T
a
, S
b
and T
b
(1 ≤ S
a
, T
a
, S
b
, T
b
≤ n, S
a
6= T
a
and
S
b
6= T
b
) .
It is guaranteed that the given graph is a tree.
The data guarantees that there will be no more than 20 groups with a value of n exceeding 400.
The data guarantees that there will be no more than 20 groups with a value of m exceeding 400.
Output
For each test case print a single integer — the identification number of this location which Serenade and
Rhapsody will meet or -1.
Page 1 of 14
Super League of Chinese College Students Algorithm Design 2023 1
China, July, 18, 2018
Example
standard input standard output
1
9 4
1 2
1 9
2 3
2 6
3 4
3 5
6 7
6 8
4 7 5 8
4 7 2 8
4 5 3 6
4 5 5 7
3
6
-1
3
Page 2 of 14
Super League of Chinese College Students Algorithm Design 2023 1
China, July, 18, 2018
Problem B. City Upgrading
Input file: standard input
Output file: standard output
Time limit: 6 seconds
Memory limit: 128 megabytes
The city where crazyzhk resides is structured as a tree. On a certain day, the city’s network needs to be
upgraded. To achieve this goal, routers need to be deployed. Each router covers the node it is placed on
and its neighboring nodes. There is a cost a
i
associated with placing a router at each node. The question
is: How can the routers be deployed at minimum cost to ensure that every node is covered?
Input
The input consists of multiple test cases. The first line contains a single integer t(1 ≤ t ≤ 1000) — the
number of test cases. Description of the test cases follows.
The first line of each test case contains a integer n (2 ≤ n ≤ 10
5
) — the number of the vertices in the
given tree.
The second line of each case are n integers a
i
(1 ≤ a
i
≤ 10
5
),denoting the cost of setting up a router at
each node.
Each of the next n − 1 lines contains two integers u and v (1 ≤ u, v ≤ n, u 6= v) meaning that there is an
edge between vertices u and v in the tree.
The data guarantees that the sum of n will not exceed 2 · 10
5
Output
For each test case print a single integer ——the minimum cost to ensure that every node is covered
Example
standard input standard output
2
7
13 20 1 20 6 9 8
1 2
1 3
2 4
2 5
3 6
5 7
4
1 17 13 4
1 2
1 3
3 4
27
5
Page 3 of 14
剩余13页未读,继续阅读
资源评论
小嗷犬
- 粉丝: 2w+
- 资源: 1334
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 海尔618算价表_七海5.20_16.00xlsx(1)(2).xlsx
- WebCrawler.scr
- 【计算机专业毕业设计】大学生就业信息管理系统设计源码.zip
- YOLO 数据集:8种路面缺陷病害检测【包含划分好的数据集、类别class文件、数据可视化脚本】
- JAVA实现Modbus RTU或Modbus TCPIP案例.zip
- 基于YOLOv8的FPS TPS AI自动锁定源码+使用步骤说明.zip
- JAVA实现Modbus RTU或Modbus TCPIP案例.zip
- 基于yolov8+streamlit的火灾检测部署源码+模型.zip
- 测试aaaaaaabbbbb
- VID20240521070643.mp4
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功