题解：CF2048E Kevin and Bipartite Graph

· · 题解

Solution fo CF2048E

前言

这道题真的有点难发现结论，感谢 @Code937 老师给我的启发，这道题我们和其他同学讨论了不下 40 分钟才出来。

题意

你有一个二分图，左边有 2n 个顶点，右边有m个顶顶，左右两两连边。

你需要给每个边染上一种颜色，总共有 n 种颜色，使得没有单色环。

求一种构造。

解法

  1. 首先观察到有无解情况。

    我们思考什么情况下会误解。

    每一条边最多可以连到 2n+m-1 个点（总共有 2n+m，要构成一棵树 所以是上述数字）。

    总共有 2nm 条边，所以当所有边都被染色是充要条件是：

    n(2n+m-1) \ge 2nm

    即：

    2n+m-1 \ge 2m

    即：

    2n > m

    所以无解的充要条件是：

    2n \le m

  2. 我们再考虑 m=2n-1 的构造方式即可（因为其他其实同理）

    我们来先思考 n=2 时的构造方案，如下：

    首先来看一种不合法的构造：

    粉色部分及不合法部分，我们观察到两边同高度有红拐角，这样就会出现问题。

    经过讨论后，我们发现第一次染红时如下染色即可：

    让我们思考第二次可不可以这么染色：

    其实显然可以，因为这让不会出现上述错误情况。

    那么这么染色保证可以染完吗？

    也是可以的，稍加计算可得这样做完全可以覆盖。

    我们还是看图：

    于是按上面模拟即可。

代码

#include <bits/stdc++.h>
// #pragma GCC optimize(3,"Ofast","inline")
namespace FastIO {
    constexpr int LEN = 1 << 20;
    inline char getchar() {
        static char buf[LEN], *l = buf, *r = buf;
        if (l == r) r = (l = buf) + fread(buf, 1, LEN, stdin);
        return l == r ? EOF : *l++;
    }
    char obuf[LEN], *p = obuf;
    inline void putchar(const char &c) {
        if (p == obuf + LEN) fwrite(p = obuf, 1, LEN, stdout);
        *p++ = c;
    }
    inline void flush() {
        fwrite(obuf, 1, p - obuf, stdout);
    }
    struct Reader {
        template<typename T> inline Reader &operator >> (T &x) {
            x = 0;
            short f = 1;
            char c = getchar();
            while (!isdigit(c)) {
                if (c == '-') f = -1;
                c = getchar();
            }
            while (isdigit(c)) x = 10 * x + (c - '0'), c = getchar();
            x *= f;
            return *this;
        }
        inline Reader &operator >> (std::string &s) {
            s.clear();
            char c = getchar();
            while (c != EOF && c <= 32) c = getchar();
            while (c > 32) {
                s += c;
                c = getchar();
            }
            return *this;
        }
    } cin;
    struct Writer {
        template<typename T> inline Writer &operator << (T x) {
            if (x < 0) putchar('-'), x = -x;
            static unsigned char tp = 0, s[40];
            do s[++tp] = x % 10 + '0', x /= 10; while (x);
            while (tp) putchar(s[tp--]);
            return *this;
        }
        inline Writer &operator << (const char *s) {
            int i = 0;
            while (s[i]) putchar(s[i++]);
            return *this;
        }
        inline Writer &operator << (const char &c) {
            putchar(c);
            return *this;
        }
        inline Writer &operator << (const std::string &s) {
            return (*this) << s.c_str();
        }
        ~Writer() {
            flush();
        }
    } cout;
}
#define cin FastIO::cin
#define cout FastIO::cout
#define endl '\n'
// #define int long long
using namespace std;
int t;
int n;
int m;
vector<pair<int,int> > ans;
int vis[3005][3005];
signed main(){
    cin>>t;
    while(t--){
        cin>>n>>m;
        if(m>=2*n){
            cout<<"No"<<endl;
            continue;
        }
        cout<<"Yes"<<endl;
        for(int i=1;i<=n;i++){
            int l=i*2-1;
            int r=1;
            while(r<=n*2-1){
                vis[l][r]=i;
                if(l>=n*2){
                    vis[1][r]=i;
                    l=0;
                }else{
                    vis[l+1][r]=i;
                }
                l++,r++;
            }
        }
        for(int i=1;i<=2*n;i++){
            for(int j=1;j<=m;j++){
                cout<<vis[i][j]<<" ";
            }
            cout<<endl;
        }
    }
    return 0;
}

完结撒花喵！