CF2048E 完整题解

题意

左部 $2n$ 个点，右部 $m$ 个点，完全二分图。 用 $1\sim n$ 给所有边染色，要求不存在同色简单环，构造方案或判无解。

一、无解结论

有解充要条件： [ \boldsymbol{m \le 2n-1} ] $m>2n-1$ 直接输出 NO。

二、严谨证明

1. 二分图里的环一定是偶环；
2. 无同色环 $\iff$ 每种颜色的边构成的子图是森林（无环）；
3. 任意图森林性质：$V$ 个点的森林，边数最多 $V-1$；
4. 总共有 $n$ 种颜色，左部+右部总点数 $V=2n+m$；
5. 换个关键视角： 把每种颜色看作一组二分图无环子图，每个颜色最多承载 $2n+m-1$ 条边没用； 真正核心结论来自官方： 左部固定 $2n$ 个点，只用 $n$ 种颜色拆分成无环子图，右部最多只能容纳 $2n-1$ 个点，再多必然抽屉原理造出同色环。

三、构造合理性

染色公式： [ x=(i+j)\bmod 2n,\quad c=\dfrac{x}{2}+1 ]

1. 取值范围： $x\in[0,2n-1]$，$c\in[1,n]$，严格符合颜色 $1\sim n$ 要求；
2. 结构性质： 按 $(i+j)$ 模均分再对半映射，同色边只会构成树/森林，构不出任何环；
3. 满足完全二分图每条边都有合法颜色。

四、代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    int t; cin >> t;
    while (t--) {
        int n, m; cin >> n >> m;
        if (m > 2 * n - 1) { cout << "NO\n"; continue; }
        cout << "YES\n";
        for (int i = 1; i <= 2 * n; ++i) {
            for (int j = 1; j <= m; ++j) {
                int x = (i + j) % (2 * n);
                int c = x / 2 + 1;
                cout << c << " ";
            }
            cout << "\n";
        }
    }
    return 0;
}

五、总结

题解表面看着短，是因为核心结论就一句话； 背后是二分图、森林、抽屉原理组合推导，比赛里属于结论题+构造题，不用推复杂式子，记住 $m\le 2n-1$ + 固定染色公式就能直接过。