#P18943. [Mladen Manev 2020 A4] network / 隐藏网络的最小生成树

[Mladen Manev 2020 A4] network / 隐藏网络的最小生成树

隐藏网络的最小生成树

这是交互题。一个隐藏的连通无向图有 NN 个顶点,编号为 11 至 NN,边权为 11 至 10610^6 的整数。求其最小生成树的边权和。

你可以指定两个非空、不相交的顶点集合 A,BA,B,询问连接这两个集合的最小权边。若有多条最小权边,交互器可以返回其中任意一条;不存在这样的边时返回三个零。

交互协议

首先读入 NN(2≤N≤10002\le N\le1000),图的边不向选手公开。

询问时输出 1 a b,其中 a=∣A∣,b=∣B∣a=|A|,b=|B|;接着分别输出 A,BA,B 中的编号,各占一行。刷新输出后,读入三个整数 u,v,wu,v,w,表示返回边的两个端点和权值,或者 0 0 0。

找到答案后,输出 0 answer,刷新输出并立即退出。

每次询问必须满足 a,b>0a,b>0、a+b≤Na+b\le N,编号合法、集合内无重复、集合间无交集。

计分

记所有询问中两个集合的大小总和分别为 SA,SBS_A,S_B。答案正确时,单个测试的得分比例为

$$\min\left(1,\frac{5001}{S_A+1}\right)\min\left(1,\frac{1000001}{S_B+1}\right).$$

满分需要 SA≤5000S_A\le5000、SB≤106S_B\le10^6。本题包总分为 100 分,所有测试捆绑计分。

注意:官方 PDF 对 AA 的总量写为 1000010000,但发布的正式 manager.cpp 使用 50005000;本题包按正式评测程序的 50005000 配置,并保留原始文件供核对。

一次交互示意

交互器先给出 4。询问 A={1,2},B={3,4}A=\{1,2\},B=\{3,4\},可能得到 1 4 1;再询问其他割,最终可以输出 0 7。这只是协议示意,实际图完全隐藏。

本地数据格式(仅供出题者)

官方 .in 包含 N,MN,M、MM 条边以及最后一项最小生成树答案。它由交互器读取,选手程序不能直接读取。原 .sol 为空,这是交互题的正常数据形式。

与原接口的关系

原题要求实现 play 并调用 get_connection/submit_security。本题包将同一交互过程转换成上述标准输入输出协议。

来源与数据说明

2020 年 Dr. Mladen Manev,A4,原题名 network。赛事资料,原文题面见附件 statement.pdf。

本题使用官方原始测试数据;评测接口按本站环境适配。总分为 100 分。