cf：E. Railway System【联通分量 + 最小生成树 + 交互式算法 + 不能成环】

分析

首先它只给出了n条点和m条边
我们要找出这m条边选取某些边使得它们形成最小生成森林
我们可以通过？来问如果存在某些边的话，当前生成森林的最大边的和
特殊地，如果我们只选一条边，那么回复的值就是这条边的长度
因此我们通过m次查询就可以直到m条边的长度了
然后我们对其进行从小到大排序，然后根据记录的（边的长度，原本边的idx）
来逐个把当前最小的边尝试加入到可行的s中（0表示不选，1表示选）
如果加入当前边之后，最小生成森林的结果和查询当前s的相同的话，说明最大的和最小的选法一致，说明只有一种选法，由于从小到大排序，所以必然是最小的
反之如果，ans + a[i][0] 和 Query(s)不相等，那必然是有大于一种选法，也就意味着必然成环，所以左边必然大，由于成环说明这条边是没有必要的，所以我们抛弃这条边即可

最后返回ans，表示选取成功的所有边的和即可

ac code

def ri():return int(input())def rl():return list(map(int, input().split()))def Query(x): print("?", x); return ri()def Solve():n, m = rl()s, a, ans = "", [], 0for i in range(m): s += "0"for i in range(m): a.append((Query(s[:i] + "1" + s[i + 1:m]), i))a.sort()for i in range(m):s = s[:a[i][1]] + "1" + s[a[i][1] + 1:]if ans + a[i][0] == Query(s):ans += a[i][0]else:s = s[:a[i][1]] + "0" + s[a[i][1] + 1:]print("!", ans)T = 1
while T:T -= 1Solve()

总结

交互式算法用Query来实现
考虑特殊情况得到每条边
由于要最小生成树，我们把边从小到大排序
一个个放进来，如果一旦成环，我们就抛弃当前边（因为这条边是没有必要的）
成环的判断就是 ans + a[i][0]表示加入这条边之后的总边长，然后Query(s)表示当前能选的生成森林的最大值
如果它们两个不等，左边表示最小的，右边表示最大的，说明必然有两种选法，也就是必然有环，因此舍去
最后排除所有成环的可能，得到ans即可

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！