CF600F Edge coloring of bipartite graph

· · 题解

分享无脑选手神人做法。

注意到答案不小于最大度数 d，猜测这就是答案，那么怎么构造呢。

最坏情况是每个点度数都是 d，一般的情况都可以补全到这种情况：只需要把两边点数补到相等，然后补一些边使得度数正确即可。可以有重边。

现在问题变成把一个正则二分图划分成 d 组完美匹配。这是经典问题：如果 d 为偶数，可以找一组欧拉回路，然后递归到两个 \frac{d}{2} 的问题。如果 d 为奇数，那么每次随机一个点出发随机游走找增广路，可以证明这样会在 O(nd+n\log n) 的复杂度内找到一组匹配。总复杂度就是 O(nd \log d + nd \log n)，不超过 O(n^2 \log n)。

我使用该做法，在代码长度约为别人 3 倍且运行时间约为别人 6 倍的情况下通过了此题，可喜可贺。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a, b, n, m;
struct Edge {
    int v, id;
    bool operator==(const Edge &b) const {
        return v == b.v && id == b.id;
    }
};
vector<Edge> e[2005];
struct EDat {
    int u, v, id;
};
EDat eP[1000005];
int epC;
int deg[2005], maxD, iC, cur[2005];
int pL[1000005], p[2005], pC;
bool vis[1000005];
void EDFS(vector<Edge> *e, int u) {
    for (int &i = cur[u]; i < e[u].size(); ) {
        auto ed = e[u][i++];
        if (vis[ed.id]) continue;
        vis[ed.id] = true;
        EDFS(e, ed.v);
        eP[++epC] = { ed.v, u, ed.id };
    }
}
mt19937 eng(363415);
int st[2005], top, mat[2005];
int cC, ans[100005];
void Solve(vector<Edge> *e) {
    if (e[1].size() & 1) {
        for (int i = 1; i <= n; i++) p[i] = i;
        for (int i = 1; i <= n * 2; i++) vis[i] = mat[i] = 0;
        shuffle(p + 1, p + n + 1, eng);
        for (int i = 1; i <= n; i++) {
            int u = p[i]; st[++top] = u;
            while (u) {
                int v;
                do v = e[u][eng() % e[u].size()].v; while (v == mat[u]);
                while (vis[v]) vis[st[top--]] = false;
                vis[st[++top] = v] = true;
                st[++top] = u = mat[v];
            }
            top--;
            for (int j = top; j; j -= 2) {
                int a = st[j], b = st[j - 1];
                mat[a] = b; mat[b] = a;
            }
            while (top) vis[st[top--]] = false;
        }
        cC++;
        for (int u = 1; u <= n; u++) {
            int v = mat[u], id = -1;
            for (auto [v, i] : e[u]) {
                if (v == mat[u]) {
                    id = i; break;
                }
            }
            if (id <= m) ans[id] = cC;
            e[u].erase(find(e[u].begin(), e[u].end(), (Edge){ v, id }));
            e[v].erase(find(e[v].begin(), e[v].end(), (Edge){ u, id }));
        }
    }
    if (e[1].empty()) return;
    for (int i = 1; i <= n * 2; i++) cur[i] = 0;
    vector<Edge> eL[2005], eR[2005];
    for (int s = 1; s <= n * 2; s++) {
        if (cur[s] < e[s].size()) EDFS(e, s);
    }
    for (int i = 1; i <= n * 2; i++) {
        eL[i].reserve(e[1].size() / 2);
        eR[i].reserve(e[1].size() / 2);
    }
    for (int i = 1; i <= epC; i++) {
        auto [u, v, id] = eP[i];
        vis[id] = false;
        if (u <= n) eL[u].push_back({ v, id }), eL[v].push_back({ u, id });
        else eR[u].push_back({ v, id }), eR[v].push_back({ u, id });
    }
    epC = 0;
    Solve(eL), Solve(eR);
}
int main() {
    scanf("%d%d%d", &a, &b, &m), n = max(a, b);
    for (int i = 1, u, v; i <= m; i++) {
        scanf("%d%d", &u, &v);
        e[u].push_back({ v + n, i });
        deg[u]++, deg[v + n]++;
    }
    iC = m;
    for (int i = 1; i <= n * 2; i++) maxD = max(maxD, deg[i]);
    printf("%d\n", maxD);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= maxD - deg[i]; j++) pL[++pC] = i;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= maxD - deg[i + n]; j++) {
            e[pL[pC--]].push_back({ i + n, ++iC });
        }
    }
    for (int u = 1; u <= n; u++) {
        for (auto [v, id] : e[u]) e[v].push_back({ u, id });
    }
    Solve(e);
    for (int i = 1; i <= m; i++) printf("%d ", ans[i]);
    return 0;
}