P5441 【XR-2】伤痕

> 长日尽处，我来到你的面前，你将看见我的伤痕，你会知晓我曾受伤，也曾痊愈。——泰戈尔《深爱你这城》

X 国经历了一场前所未有的大地震，人们伤痕累累，整个国家破碎不堪。 为了帮助人们痊愈，也为了让 X 国能够生存下去，X 国国王决定重建 X 国。 国王决定先建造 $n$ 座城市，由于国王喜欢奇数，所以 $n$ 为奇数。 城市建造完后，需要给每两座城市之间都修建一条道路，即一共需要修建 $\frac{n(n-1)}{2}$ 条道路。 不过，修建双向道路的成本太高了，建造完 $n$ 座城市后剩下的经费最多只够修建 $n$ 条双向道路，而其余的道路只能修建成单向的。好在方向并不会影响修建单向道路所需的费用，因此所有单向道路的方向可以任意决定。 另外，等到重建完成后，国王决定将 $4$ 座城市钦定为 X 国的核心城市。为促进 X 国的发展，这 $4$ 座核心城市中的任意两座城市，必须能够在不经过非核心城市的情况下相互到达。 国王希望，你能够给他一种道路修建方案，使重建完成后选择 $4$ 座核心城市的方案数最大化。

无

无

【样例 $1$ 说明】 由于一共只有 $3$ 个点，所以选择 $4$ 座核心城市的方案数一定为 $0$，那么只需要保证修建方案满足条件即可。 【样例 $2$ 说明】  显然，在 $5$ 个点中任意选 $4$ 个点，都满足核心城市的条件，因此方案数最大为 $5$。 【数据规模与约定】 本题一共有 $50$ 个测试点，每个测试点 $2$ 分。对于第 $i$ 个测试点，$n = 2i - 1$。 对于每个测试点，有五种可能的结果： 1. 输出格式错误，包括：没有输出最大方案数、没有输出邻接矩阵、输出了多余的信息等。你将无法得到该测试点的任何分数，同时我们无法确定 Special Judge 的返回结果。 2. 没有正确计算最大方案数，即使构造的道路修建方案是正确的。你将得到该测试点 $0\%$ 的分数（即 $0$ 分），Special Judge 将会返回 WA 的结果，同时输出 “The answer is wrong.” 3. 正确计算了最大方案数，但是构造的道路修建方案不满足条件，包括：邻接矩阵中有不为 $0$ 或 $1$ 的数、有自环、有两座城市中没有道路、有多于 $n$ 条双向道路等。你将得到该测试点 $50\%$ 的分数（即 $1$ 分），Special Judge 将会返回 WA 的结果，同时输出 “The answer is correct, but your plan breaks the rules.” 4. 正确计算了最大方案数，构造的道路修建方案满足条件但没有将选择 $4$ 座核心城市的方案数最大化。你将得到该测试点 $50\%$ 的分数（即 $1$ 分），Special Judge 将会返回 WA 的结果，同时输出 “The answer is correct, but your plan is wrong.” 5. 正确计算了最大方案数，同时正确构造了道路修建方案。你将得到该测试点 $100\%$ 的分数（即 $2$ 分），Special Judge 将会返回 AC 的结果，同时输出 “The answer is correct.”