题解：CF2172N New Kingdom

ddxrS · 2025-11-20 00:36:43 · 题解

题目大意

给定三个整数 n,k,b。构造一张有 m(0\le m\le 5n) 条边的连通简单无向图，满足有 k 个点的度数为奇数，有 b 条边是割边 。

解法

这道题思考起来并不困难，但是存在一定数量的 corner case，一般可以通过跑出较小范围的所有数据来进行调试。

首先，因为总度数为 2m 是偶数，所有奇数点个数一定是偶数，当 k 是奇数时无解。

有 b 条边是割边，相当于要求缩点后形成一棵有 b+1 个节点的树。

同时，当 b=n-2 时，必然存在一个边双包含两个节点，但这样的边双一定存在重边，所以无解。

Part 1（k=0）

缩点后得到的树，其叶子节点的度数必为奇数，其在原图中对应的一个边双至少存在一个点度数为奇数。

所以，当 k=0 时，只能存在一个边双，也就是 b=0，当 b>0 时无解。然后：

• 当 n=1 时，只有一个点，不需要连边。
• 当 n=2 时，必须连成一个边双，如上面所说，必须有边 (1,2) 和 (2,1)，此时出现重边，所以无解。
• 当 n\ge 3 时，只需要用 n-1 条边将所有点连成一个环即可。

Part 2（b=0）

此时只有一个边双，可以用 n-1 条边将所有点连成一个环来构造边双。

接下来，我们考虑构造出 k 个度数为奇数的点。有如下构造方式：

• 选择环上 \frac{k}{2} 对互不同相同的点对，对每个点对内连边，可以产生 k 个度数为奇数的点。

注意，当 n=3,k=2 时，我们需要在环上连一个点对，但此时无论选择哪两个点都会产生重边，所以无解。

Part 3（b+1>k）

此时是边双个数比度数为奇数的点的个数多的情况。

我们可以采取这样的构造方式：

如上图（n=12,k=6,b=8 时的构造）：

• 红色部分，我们通过构造一个菊花来满足有 k 个奇数点的限制。
• 橙色部分，我们通过构造一条链来满足多余的边双的限制。
• 黄色部分，仅通过前面两个部分我们可能无法将 n 个点全部用完，所以我们可以通过构造一个环来将剩下的点用完。

Part 4（b+1=k）

此时，相较于 b+1>k 的构造方式，我们只需要去除橙色部分即可。也就是说，我们的构造方式是一个环形成的边双上连接一个菊花。

Part 5（b+1<k）

此时，我们能够使用的边双的数量要少于奇数点的个数，也就是说，我们需要使用 Part 2 的做法在边双内构造出若干度数为奇数的点。

我们希望每个边双的环尽可能大，这样才能构造出尽可能多的度数为奇数的点。贪心的考虑，我们使用 Part 4 中的做法，即构造一个边双，上面连 b 个点的菊花。

如图（n=12,k=8,b=4 时的构造）。

我们只需要在大环中连 \frac{k-b}{2} 对点，就可以构造出所有 k 个度数为奇数的点。

注意一个特殊情况：大环中包含 3 个节点。此时我们的构造方式并不适用，因为三个节点的环会连出重边。

首先，当 n=4,b=1 时无解。其它情况：

• 构造一个包含节点 1,2,3 的环。
• 在 2,3 上分别连接一个节点，在 1 上连接剩下 n-5 个节点即可。

以上，我们的构造方案边数不超过 \frac{3}{2}n，可以通过此题。