「AtCoder」「JSC 2019 Qual D」Classified

有一张 \(n\) 个点的无向完全图 \(G=(V,E)\)，你需要给每条边定一个正整数权值，使得不存在一条回路满足这条回路上的所有边权相等且回路长度为奇数。

你需要最小化最大的权值。请你输出一个解。

\(n\le 500\)

题目里的条件相当于对于每一个权值 \(x\)，记 \(E'\) 为所有边权等于 \(x\) 的边组成的边集，满足 \(G'=(V,E')\) 是二分图。我们把 \(G'\) 叫做权值为 \(x\) 的子图。

先猜一个结论，假设边权的最大值为 \(k\)，则最大的有解的 \(n\) 为 \(2^k\)。用数学归纳法可以证明：

显然 \(k=1,n=2\) 是有解的，\(k=1,n=3\) 是无解的。 假设我们已经证明了 \(k=t-1,n=2^{t-1}\) 是有解的，\(k=t-1,n=2^{t-1}+1\) 是无解的，我们要证明 \(k=t,n=2^t\) 是有解的，\(k=t,n=2^t+1\) 是无解的。 \(k=t,n=2^t\) 是有解的很好证明，我们只要把这 \(n\) 个点分成两个大小为 \(2^{t-1}\) 的集合，两个集合之间的边边权为 \(t\)，然后只要使得两个集合内部的边边权最大值为 \(t-1\)，则权值为 \(t\) 的子图已经符合条件。而对于两个集合，变成了两个相同的子问题，即 \(k=t-1,n=2^{t-1}\)，我们已经证明了这是有解的，所以 \(k=t,n=2^t\) 也是有解的。 \(k=t,n=2^t+1\) 是无解的也很好证明。假设它是有解的，那么答案中权值为 \(t\) 的子图一定是二分图且这个二分图的两个集合分别有解。由于总点数是 \(2^t+1\)，那么这个二分图的两个集合中一定有一个集合大小 \(\ge 2^{t-1}+1\)。已经证明 \(k=t-1,n=2^{t-1}+1\) 是无解的，与“这个二分图的两个集合分别有解”矛盾，所以 \(k=t,n=2^t+1\) 是无解的。

所以答案为 \(\lceil \log_2 n\rceil\)。考虑构造一个解。我们只要按照一个点的编号二进制下从右往左的第 \(\lceil \log_2 n\rceil\) 位是 \(0\) 还是 \(1\) 分成两个集合，这两个集合之间的边边权设为 \(\lceil \log_2 n\rceil\)，然后递归处理。

我们发现，两个点 \(i,j\) 的边的边权其实就是 \(i\) 与 \(j\) 最高的不同的位从右往左的编号，也就是 \(\lfloor \log_2 (i \text{ xor }j)\rfloor+1\)。

时间复杂度 \(O(n^2)\)。