神仙构造题。写一下 pb 讲的做法。
考虑极差不超过 2 这个限制。可以把每条边 u,v ,令 u<v ,则变成 u,v+n 的一条边,也就是拆成一个二分图。
考虑在这个图上染色,然后再把 u,u+n 合并起来。如果在这个得到的二分图上可以染色使得每个点极差不超过 1 ,那么合并后一定可以让每个点极差不超过 2 。
下面将说明这样的合法的染色方案一定存在。假设一个点 u 的度数是 ak+b ,那么我们可以把一个点拆成 a+1 个点,然后前 a 个点分别得到原二分图上 u 的任意 k 个出边,最后一个得到 b 个出边。然后我们就需要染色后使得每个点的的所有出边颜色不同。
考虑一条边一条边进行染色。假设当前边的两端是 u,v 。现在我们任意找到 u,v 的一对还没有用过的颜色 cu,cv 。如果有 cu=cv ,显然可以直接给这条边染色。否则,我们把这条边置为 cu ,然后去寻找一条 v 的出边使得颜色也是 cu ,假设这条边连向 w ,把这条边置为 cv ,然后再去找 w 的一条出边使得这条出边是 cu ,再置为 cv … 就这么一直操作下去。注意,我们寻找的颜色一定是 cu,cv 之一。大致过程长成这样:
这么一直操作下去,最后一定不会出现环。如果出现了,显然必然是一个偶环。画图一下会发现
这种情况必然对应着图中的虚线边,这就意味着 cu 并不是一个合法的颜色,或者意味着之前的染色方案并不合法。因此,一定不会找到环。所以按照这样的方式一直染色即可找到一组合法的方案。
最坏情况下,对于每条边可能都需要遍历整张图,复杂度是 O(mn2) 大概,可以通过这个题。
cpp
1 | typedef long long ll; |