题解：AT_abc317_g [ABC317G] Rearranging

cosf · 2025-11-05 08:27:48 · 题解

二分图边着色

对于一个无向图，定义一个着色方案为给每一条边进行染色，使得每一个点的所有邻边颜色不同。记这样需要的最少颜色数量为 \chi(G)。

Vizing 定理：

设图 G 中具有最大度数的点的度数为 d(G)，则有 d(G) \le \chi(G) \le d(G) + 1。称左侧取等的为一类图，右侧取等的为二类图。

对于一般图，判别它属于哪一类是 NP 困难的。但是，所有的二分图都属于一类图。

对于二分图有构造性证明。

设二分图的左右部为 X, Y。考虑从无边图开始，依次往图中加入一条边，并调整图的着色。

我们给每种颜色进行标号。当我们加入边 (x, y) 时，设 c_x, c_y 分别为 x, y 邻边中没有出现的最小颜色（就是颜色中的 \operatorname{mex}）。

如果 c_x = c_y，那么将这条边的颜色设为 c_x 即可。

否则假设 c_x \lt c_y，我们需要将与 y 相邻的 c_x 边颜色改为 c_y。对此，我们可以找最长的一条增广路 y - x_1 - y_1 - x_2 - y_2 - \dots，满足 y_i - x_{i + 1} 边颜色为 c_x，x_i - y_i 边颜色为 c_y。这样的增广路显然是唯一的，并且不包含 x（因为 x 没有 c_x 边，自然不会有某个 y_i 连向它）。然后，我们将这些边的颜色翻转即可。

然后就可以在 c_x, c_y 之间连边了。

容易发现 c_x, c_y 在 x, y 度数还没达到 d(G) 之前都会 \le d(G)，因此最终用到的颜色数量是 d(G)。\square

:::info[模板题与代码]{open}

CF600F Edge coloring of bipartite graph

真的就是模板。

#include <iostream>
#include <cstring>
using namespace std;

#define MAXN 2005
#define MAXM 200005

struct Edge
{
    int u, v;
    int col;
} e[MAXM];
int idx = 1;
int h[MAXN], d[MAXN];
int fr[MAXN][MAXN]; // fr[i][c] 表示点 i 邻边中颜色为 c 的那条
int res[MAXN][MAXN];

void add(int u, int v)
{
    e[++idx] = {h[u], v};
    h[u] = idx;
    d[u]++;
    e[++idx] = {h[v], u};
    h[v] = idx;
    d[v]++;
}

int a, b, m;

void dfs(int p, int o, int n) // 寻找增广路，将 p 中颜色为 o 的出边改成 n
{
    if (!fr[p][o])
    {
        fr[p][n] = 0;
        return;
    }
    int ei = fr[p][o];
    int u = e[ei].v;
    dfs(u, n, o);
    fr[p][n] = ei;
    fr[u][n] = ei ^ 1;
    e[ei].col = e[ei ^ 1].col = n;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> a >> b >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        add(u, v + a);
    }
    int mx = 0;
    for (int i = 1; i <= a + b; i++)
    {
        mx = max(mx, d[i]);
    }
    cout << mx << '\n';
    for (int i = 2; i < idx; i += 2)
    {
        int u = e[i].v, v = e[i ^ 1].v;
        int lu = 1, lv = 1;
        while (fr[u][lu])
        {
            lu++;
        }
        while (fr[v][lv])
        {
            lv++;
        }
        if (lu < lv)
        {
            dfs(v, lu, lv);
        }
        if (lv < lu)
        {
            dfs(u, lv, lu);
        }
        int l = min(lu, lv);
        fr[u][l] = i ^ 1;
        fr[v][l] = i;
        e[i].col = e[i ^ 1].col = l;
    }
    for (int i = 2; i < idx; i += 2)
    {
        cout << e[i].col << ' ';
    }
    cout << '\n';
    return 0;
}

UVA10615 Rooks

另一个模板题，边以邻接矩阵的形式给出。

#include <iostream>
#include <cstring>
using namespace std;

#define MAXN 305
#define MAXM 100005

// Vizing Theorem: Chi(G) = max Deg(i)

struct Edge
{
    int u, v;
    int col;
} e[MAXM];
int idx = 1;
int h[MAXN], d[MAXN];
int fr[MAXN][MAXN];
int res[MAXN][MAXN];

void add(int u, int v)
{
    e[++idx] = {h[u], v};
    h[u] = idx;
    d[u]++;
    e[++idx] = {h[v], u};
    h[v] = idx;
    d[v]++;
}

int n;

void dfs(int p, int o, int n)
{
    if (!fr[p][o])
    {
        fr[p][n] = 0;
        return;
    }
    int ei = fr[p][o];
    int u = e[ei].v;
    dfs(u, n, o);
    fr[p][n] = ei;
    fr[u][n] = ei ^ 1;
    e[ei].col = e[ei ^ 1].col = n;
}

void solve()
{
    memset(e, 0, sizeof(e));
    memset(h, 0, sizeof(h));
    memset(d, 0, sizeof(d));
    memset(fr, 0, sizeof(fr));
    memset(res, 0, sizeof(res));
    idx = 1;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = n + 1; j <= 2 * n; j++)
        {
            char ch;
            cin >> ch;
            if (ch == '*')
            {
                add(i, j);
            }
        }
    }
    int mx = 0;
    for (int i = 1; i <= 2 * n; i++)
    {
        mx = max(mx, d[i]);
    }
    cout << mx << '\n';
    for (int i = 2; i < idx; i += 2)
    {
        int u = e[i].v, v = e[i ^ 1].v;
        int lu = 1, lv = 1;
        while (fr[u][lu])
        {
            lu++;
        }
        while (fr[v][lv])
        {
            lv++;
        }
        if (lu < lv)
        {
            dfs(v, lu, lv);
        }
        if (lv < lu)
        {
            dfs(u, lv, lu);
        }
        int l = min(lu, lv);
        fr[u][l] = i ^ 1;
        fr[v][l] = i;
        e[i].col = e[i ^ 1].col = l;
    }
    for (int i = 2; i < idx; i += 2)
    {
        int u = e[i].v - n, v = e[i ^ 1].v;
        res[v][u] = e[i].col;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cout << res[i][j] << ' ';
        }
        cout << '\n';
    }
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

:::

本题题解

每一列都是一个排列，自然想到这是一个完美匹配状物。

我们对行和数值建点，对于给定的 A_{i, j}，我们让行 i 和值 A_{i, j} 建边，这样可以得到一个度数为 M 的正则二分图。

我们只需要将其拆成 M 个完美匹配即可解决问题。

:::info[正则二分图必有完美匹配的证明]

由 Hall 定理，一个二分图有完美当且仅当对于左部点的任意一个子集 S，和与其直接相邻的右部点集 N(S) 满足 |N(S)| \ge |S|。

在正则二分图中，S 内部点的度数和 \ge M \times |S|。若 |N(S)| \lt |S|，则 N(S) 内部点的度数和 \lt M \times |S|，这与 N(S) 包含所有与 S 相邻的右部点矛盾。\square

:::

至于怎么求，显然我们对这个图进行边着色即可。

:::success[代码]

#include <iostream>
using namespace std;

#define MAXN 205
#define MAXM 100005

int n, m;

struct Edge
{
    int u, v, rc;
    int col;
} e[MAXM];
int h[MAXN];
int idx = 1;

int fr[MAXN][MAXN], ed[MAXN][MAXN];

void add(int u, int v, int rc)
{
    e[++idx] = {h[u], v, rc};
    h[u] = idx;
    e[++idx] = {h[v], u, rc};
    h[v] = idx;
}

void dfs(int p, int f, int t)
{
    if (!fr[p][f])
    {
        fr[p][t] = 0;
        return;
    }
    int ei = fr[p][f];
    int u = e[ei].v;
    dfs(u, t, f);
    fr[p][t] = ei;
    fr[u][t] = ei ^ 1;
    e[ei].col = e[ei ^ 1].col = t;
}

int a[MAXN][MAXN];

int main()
{
    cin >> n >> m;
    idx = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            int v;
            cin >> v;
            a[i][j] = v;
            v += n;
            add(i, v, j);
            int ic = 1, vc = 1;
            while (fr[i][ic])
            {
                ic++;
            }
            while (fr[v][vc])
            {
                vc++;
            }
            if (ic < vc)
            {
                dfs(v, ic, vc);
            }
            if (ic > vc)
            {
                dfs(i, vc, ic);
            }
            int c = min(ic, vc);
            fr[i][c] = idx ^ 1;
            fr[v][c] = idx;
            e[idx].col = e[idx ^ 1].col = c;
        }
    }
    cout << "Yes\n";
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cout << a[i][e[fr[i][j]].rc] << ' ';
        }
        cout << '\n';
    }
    return 0;
}

:::

拓展

:::info[AGC037D]

题目链接：AGC037D Sorting a Grid

观察到在最后一步前，我们要使得同一行内的数都在 [(i-1)M + 1, iM] 之间，所以子先将所有数替换成其最后所在行的编号。

则第一步中，我们重排列行，使得每一列都是一个排列。

第二步，我们重排列列，使得每一列都是 1, \dots, N 依次递增。此时每一个数都已经位于它目标的行里面了。

第三步，我们重排列行，最终得到答案。

后面两步是容易的，第一步就是二分图着色。

#include <algorithm>
#include <iostream>
using namespace std;

#define MAXN 205
#define MAXM 100005

int n, m;

struct Edge
{
    int u, v, rc;
    int col;
} e[MAXM];
int h[MAXN];
int idx = 1;

int fr[MAXN][MAXN], ed[MAXN][MAXN];

void add(int u, int v, int rc)
{
    e[++idx] = {h[u], v, rc};
    h[u] = idx;
    e[++idx] = {h[v], u, rc};
    h[v] = idx;
}

void dfs(int p, int f, int t)
{
    if (!fr[p][f])
    {
        fr[p][t] = 0;
        return;
    }
    int ei = fr[p][f];
    int u = e[ei].v;
    dfs(u, t, f);
    fr[p][t] = ei;
    fr[u][t] = ei ^ 1;
    e[ei].col = e[ei ^ 1].col = t;
}

int a[MAXN][MAXN], b[MAXN][MAXN], c[MAXN];

int main()
{
    cin >> n >> m;
    idx = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            int v;
            cin >> v;
            a[i][j] = v;
            v = (v - 1) / m + 1 + n;
            add(i, v, j);
            int ic = 1, vc = 1;
            while (fr[i][ic])
            {
                ic++;
            }
            while (fr[v][vc])
            {
                vc++;
            }
            if (ic < vc)
            {
                dfs(v, ic, vc);
            }
            if (ic > vc)
            {
                dfs(i, vc, ic);
            }
            int c = min(ic, vc);
            fr[i][c] = idx ^ 1;
            fr[v][c] = idx;
            e[idx].col = e[idx ^ 1].col = c;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cout << (b[i][j] = a[i][e[fr[i][j]].rc]) << ' ';
        }
        cout << '\n';
    }
    for (int j = 1; j <= m; j++)
    {
        for (int i = 1; i <= n; i++)
        {
            c[i] = b[i][j];
        }
        sort(c + 1, c + n + 1);
        for (int i = 1; i <= n; i++)
        {
            b[i][j] = c[i];
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cout << b[i][j] << ' ';
        }
        cout << '\n';
    }
    return 0;
}

:::

:::info[P9070]

题目链接：P9070 [CTS2023] 琪露诺的符卡交换

如果我们有办法重排每一行，使得每一列都是一个排列的话，那么交换 (i, j) 和 (j, i) 就可以使每一行都是一个排列。

因此边着色即可。

#include <iostream>
using namespace std;

#define MAXN 405
#define MAXM 200005

int n;

struct Edge
{
    int u, v, rc;
    int col;
} e[MAXM];
int h[MAXN];
int idx = 1;

int fr[MAXN][MAXN], ed[MAXN][MAXN];

void add(int u, int v, int rc)
{
    e[++idx] = {h[u], v, rc};
    h[u] = idx;
    e[++idx] = {h[v], u, rc};
    h[v] = idx;
}

void dfs(int p, int f, int t)
{
    if(!fr[p][f])
    {
        fr[p][t] = 0;
        return;
    }
    int ei = fr[p][f];
    int u = e[ei].v;
    dfs(u, t, f);
    fr[p][t] = ei;
    fr[u][t] = ei ^ 1;
    e[ei].col = e[ei ^ 1].col = t;
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= 2 * n; i++)
    {
        h[i] = 0;
        for (int j = 1; j <= n; j++)
        {
            fr[i][j] = 0;
        }
    }
    idx = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            int v;
            cin >> v;
            v += n;
            add(i, v, j);
            int ic = 1, vc = 1;
            while (fr[i][ic])
            {
                ic++;
            }
            while (fr[v][vc])
            {
                vc++;
            }
            if (ic < vc)
            {
                dfs(v, ic, vc);
            }
            if (ic > vc)
            {
                dfs(i, vc, ic);
            }
            int c = min(ic, vc);
            fr[i][c] = idx ^ 1;
            fr[v][c] = idx;
            e[idx].col = e[idx ^ 1].col = c;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            ed[i][j] = e[fr[i][j]].rc;
        }
    }
    cout << n * (n - 1) / 2 << '\n';
    for (int i = 1; i < n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            cout << i << ' ' << ed[i][j] << ' ' << j << ' ' << ed[j][i] << '\n';
        }
    }
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

:::