#P18943. [Mladen Manev 2020 A4] network / 隐藏网络的最小生成树
[Mladen Manev 2020 A4] network / 隐藏网络的最小生成树
隐藏网络的最小生成树
这是交互题。一个隐藏的连通无向图有 个顶点,编号为 至 ,边权为 至 的整数。求其最小生成树的边权和。
你可以指定两个非空、不相交的顶点集合 ,询问连接这两个集合的最小权边。若有多条最小权边,交互器可以返回其中任意一条;不存在这样的边时返回三个零。
交互协议
首先读入 (),图的边不向选手公开。
询问时输出 1 a b,其中 ;接着分别输出 中的编号,各占一行。刷新输出后,读入三个整数 ,表示返回边的两个端点和权值,或者 0 0 0。
找到答案后,输出 0 answer,刷新输出并立即退出。
每次询问必须满足 、,编号合法、集合内无重复、集合间无交集。
计分
记所有询问中两个集合的大小总和分别为 。答案正确时,单个测试的得分比例为
$$\min\left(1,\frac{5001}{S_A+1}\right)\min\left(1,\frac{1000001}{S_B+1}\right).$$满分需要 、。本题包总分为 100 分,所有测试捆绑计分。
注意:官方 PDF 对 的总量写为 ,但发布的正式 manager.cpp 使用 ;本题包按正式评测程序的 配置,并保留原始文件供核对。
一次交互示意
交互器先给出 4。询问 ,可能得到 1 4 1;再询问其他割,最终可以输出 0 7。这只是协议示意,实际图完全隐藏。
本地数据格式(仅供出题者)
官方 .in 包含 、 条边以及最后一项最小生成树答案。它由交互器读取,选手程序不能直接读取。原 .sol 为空,这是交互题的正常数据形式。
与原接口的关系
原题要求实现 play 并调用 get_connection/submit_security。本题包将同一交互过程转换成上述标准输入输出协议。
来源与数据说明
2020 年 Dr. Mladen Manev,A4,原题名 network。赛事资料,原文题面见附件 statement.pdf。
本题使用官方原始测试数据;评测接口按本站环境适配。总分为 100 分。