题解 CF550D 【Regular Bridge】

· · 题解

首先考虑把桥扔掉，原图变为两个联通块，其中每个联通块中有一个点度数为k-1,其他的点度数为k。下面考虑构造其中一个联通块。

不妨令该联通块点数为n。 注意到当k为偶数时，这一个联通块中的总度数应该是nk-1，是一个奇数，而由于是无向图，每条边对总度数的贡献是2，总度数应该是偶数，产生矛盾。从而k为偶数时是无解的。

k为奇数时，令n=2k-1，并且将所有点列成三排：第一排和第二排分别有k-1个点，第三排有一个。第三排与第二排之间两两连边，第二排与第一排之间两两连边，再令第一排中第2t-1与第2t个连边（1<=t<=(k-1)/2）。不难发现这样一来第二排与第一排每个点的度数是k，第三排一个点度数为k-1，符合我们的需求。另一个联通块类似即可，不要忘记将两个联通块中度数为k-1的点相连作为桥。

复杂度是O(k^2)的，可以通过；代码简单，略去。