251105 模拟赛

T1

简单分讨即可。

T2

简单贪心即可。

T3

有一个 \(01\) 边权的简单无向连通图，你是交互库。每次 Alice 会询问你一个边的集合，表示询问将这些边的边权改为 \(0\)，原图的最小生成树是多少。问最少需要改多少条边的边权，才能让 Alice 猜出来。

\(n\le 14\)

考虑 Alice 会怎么猜。Alice 可以把每条边都问一遍，如果一条 \(1\) 边 \((u,v)\) 满足图上不存在 \(u\to v\) 边权和为 \(0\) 的路径，那么问出的最小生成树会减小 \(1\)，因此 Alice 就知道这条边的边权是 \(1\) 了。否则如果存在，那么 Alice 一定不能判断出这条边的边权。因此我们就得到了合法的充要条件：\(0\) 边组成的图是森林，\(1\) 边两端在不同 \(0\) 边的连通块内。

进行状压 dp，每次转移枚举一个 \(0\) 边组成的树，判断其是否连通以及其中的边数是否合法。时间复杂度 \(O\big(3^n+2^npoly(n)\big)\)。

T4

不会