Tác giả: Hoàng Xuân Nhật

Bài này có ít nhất 2 cách làm, dưới đây mình sẽ trình bày 2 cách mà mình hiểu.

Kiến thức cần biết

Đầu tiên, dễ nhận thấy ngay là bài này có thể mô hình dưới dạng đồ thị hai phía. Nếu bạn không nhận ra điều này, bạn cần làm nhiều bài tập về chủ đề này hơn.

Trong lý thuyết đồ thị, có khá nhiều kết quả về lý thuyết mà bạn nên biết. Để làm bài này, bạn cần phải hiểu rõ thuật toán tìm cặp ghép cực đại trên đồ thị hai phía. Bạn có thể tìm đọc thuật toán này ở sách Giải thuật lập trình của thầy Lê Minh Hoàng.

Mô hình đồ thị

Trong bài toán này, ta đưa về đồ thị hai phía như sau: bên trái có ~m~ đỉnh, bên phải có ~n~ đỉnh, đỉnh thứ ~i~ ở bên trái nối với đỉnh thứ ~j~ ở bên phải nếu dòng ~i~ cột ~j~ cần lắp đèn.

Tô màu đồ thị

Phần này tập trung vào việc tìm ra con số p mà đề bài yêu cầu.

Trong lý thuyết đồ thị có nhiều bài toán liên quan đến tô màu đồ thị. Bài toán ta đang giải chính là bài toán tô màu cạnh. Cụ thể bài toán như sau: cho một đồ thị, ta phải gán cho mỗi cạnh một màu sao cho không có hai cạnh cùng kề một đỉnh nào có cùng màu. Với mỗi đồ thị, số màu tối đa cần phải dùng để tô màu đỉnh đồ thị G được gọi là chỉ số màu (chromatic index), hay số màu cạnh (edge chromatic number) của đồ thị đó, kí hiệu là ~χ'(G)~.

Gọi ~Δ(G)~ là bậc lớn nhất của đồ thị ~G~. Ta dễ dàng chứng minh được ~χ'(G) \geq Δ(G)~.

Liệu đây có phải chính là đáp án? Bằng trực giác, ta có cảm giác rằng con số này đã rất gần với số lượng màu thực tế cần. Ta có thể suy đoán rằng ~χ'(G) = Δ(G)~, ít nhất là trong trường hợp đồ thị hai phía. Dù việc chứng minh điều này không hề đơn giản, những suy nghĩ mang tính chất "trực giác" trên ít nhất cho bạn một hướng đi để giải bài toán.

Định lý 1 (Vizing): Với mọi đơn đồ thị vô hướng ~G~, ~Δ(G) \leq χ'(G) \leq Δ(G) + 1~.

Woa, giá như bạn biết điều này sớm hơn! Trên thực tế, việc biết những định lý như thế này có thể là cứu cánh của bạn khi làm những bài có liên quan. Bạn có thể đọc phần chứng minh của định lý này tại đây. Phần chứng minh này cũng khá giống với lời giải 2, nên bạn có thể tham khảo lời giải 2 trước khi đọc chứng minh.

Định lý 2 (Kőnig): Với mọi đồ thị hai phía ~G~, ~χ'(G) = Δ(G)~.

Định lý này có tên là định lý Kőnig về tô màu cạnh (Kőnig line coloring theorem). Ta sẽ chứng minh định lý này bằng cách giải bài toán này. Thật vậy, mọi lời giải chính xác của bài toán này là một lời giải xây dựng (constructive proof) cho định lý Kőnig, hay nói cách khác, ta chứng minh định lý Kőnig đúng bằng cách chỉ ra một cách tô màu cho mỗi đồ thị.

Lời giải 1

Lời giải sau thiên về Toán. Đầu tiên, ta cần chứng minh bổ đề sau:

Bổ đề 1: Trong một đồ thị hai phía ~G~ với bậc tối đa của một đỉnh bằng ~D~, tồn tại một bộ ghép phủ tất cả các đỉnh có bậc bằng ~D~.

Chứng minh: gọi ~L~ là tập hợp các đỉnh có bậc bằng ~D~ thuộc một bên của đồ thị hai phía, và ~R~ là tập hợp các đỉnh có bậc bằng ~D~ thuộc bên còn lại. Ta chứng minh tồn tại một bộ ghép phủ ~L~ bằng định lý Hall: xét một tập con ~S~ của ~L~. Gọi ~N_g(S)~ là tập các đỉnh có thể tới được ~S~ thông qua 1 cạnh trong ~G~. Theo định lý Hall, bộ ghép phủ ~L~ tồn tại nếu ~|S| \leq |N_g(S)|~. Thật vậy, vì số cạnh kề ~S~ và ~N_g(S)~ là bằng nhau và bằng ~|S| * D~, nếu ~|S| > |N_g(S)|~ sẽ dẫn tới việc bậc lớn nhất trong ~N_g(S)~ là lớn hơn ~D~, đây là một điều mâu thuẫn vì ta giả sử ~D~ là bậc lớn nhất của đồ thị, từ đó suy ra điều phải chứng minh.

Tương tự, ta có thể chứng minh bộ ghép phủ ~R~ tồn tại. Lấy hợp của hai bộ ghép này, ta được một bộ ghép phủ tất cả các đỉnh có bậc bằng ~D~.

Từ bổ đề 1, ta sẽ đi chứng minh định lý Kőnig bằng phương pháp quy nạp trên ~Δ(G)~.

• Nếu ~Δ(G) = 0~, hay đồ thị là rỗng, hiển nhiên ~χ'(G) = 0~.
• Ngược lại, giả sử ta giải được bài toán với mọi đồ thị ~G'~ có ~Δ(G') = K - 1~, ta giải bài toán cho đồ thị có ~Δ(G) = K~. Ta tìm một bộ ghép phủ tất cả các đỉnh có bậc bằng ~K~. Theo bổ đề 1, bộ ghép như vậy luôn tồn tại. Ta tô tất cả các cạnh trong bộ ghép này cùng một màu, sau đó loại chúng ra khỏi đồ thị. Lúc này, ta được một đồ thị mới ~G'~ với ~Δ(G') = K - 1~. Theo giả thiết quy nạp, ta có thể tô đồ thị ~G'~ bằng ~K - 1~ màu, cộng với một màu ta vừa tô là ~K~ màu, từ đó suy ra điều phải chứng minh.

Cách chứng minh này cũng cho ta luôn thuật toán để tô màu: ta lần lượt tìm bộ ghép phủ các đỉnh có bậc tối đa, sau đó tô màu cho chúng, loại ra khỏi đồ thị và lặp lại. Tuy nhiên, để cài đặt được phần tìm bộ ghép, chúng ta cần có một chút chỉnh sửa so với thuật tìm bộ ghép cực đại tiêu chuẩn.

Để giải quyết triệt để điều kiện bộ ghép phủ một số đỉnh, ta có thể biến bài toán thành bài toán luồng với cạnh có chặn dưới, bạn có thể đọc thêm bài toán này ở đây. Tuy nhiên, cách xử lý này khá cồng kềnh, và chúng ta tìm một giải pháp đơn giản hơn. Thông thường, để tìm được luồng/bộ ghép cực đại, cốt lõi là việc tìm được một đường tăng luồng (augmenting path). Nếu bạn không hiểu đường tăng luồng là gì, bạn có thể đọc thêm về bài toán luồng cực đại tại đây. Trong trường hợp này, ta định nghĩa đường luân phiên (alternating path) là một đường xen kẽ cạnh không trong bộ ghép và cạnh trong bộ ghép, còn đường tăng luồng là đường luân phiên bắt đầu và kết thúc ở đỉnh chưa được ghép.

Trong cách cài đặt thuật toán tìm bộ ghép cực đại trên đồ thị hai phía điển hình, thường ta chỉ tìm đường tăng luồng với các đỉnh của một bên. Điều này giúp ta tìm được bộ ghép cực đại, nhưng không tìm được bộ ghép phủ các đỉnh có bậc cực đại như trong thuật toán trên.

Chú ý rằng công cụ ta có là một hàm ~f(u)~ có thể tìm được một đường tăng luồng bắt đầu từ ~u~. Hàm đó thường được cài đặt như sau:

bool dfs(int u, int tme)
{
    if (vst[u] == tme) return false;
    vst[u] = tme;
    for (int v : g[u])
        if (!match[v] || dfs(match[v], tme)) {
            match[u] = v;
            match[v] = u;
            return true;
        }
    return false;
}

Ta có thể chỉnh sửa bằng cách gọi ~f(u)~ cho ~\forall u \in L~. Nhưng còn ~R~ thì sao? Ta có thể gọi ~f(u)~ cho ~\forall u \in R~, nhưng điều này không đúng; ta sẽ tìm ~L + R~ đường tăng luồng, tuy nhiên, theo chứng minh của bổ đề 1, ta phải tìm giao của hai bộ ghép, do đó số đường tăng luồng có thể nhỏ hơn ~L + R~.

Mấu chốt ở đây là cho tập ~R~, với ~u \in R~ ta có thể tìm đường tăng luồng hoặc đường luân phiên bắt đầu từ ~u~ và kết thúc ở ~t \notin R~. Khi làm thế, ta "đổi hướng" một đường tăng luồng trước đó từ ~t~ sang ~u~, tăng độ phủ của tập ~R~. Vì bộ ghép luôn tồn tại nên với mỗi ~u \in R~ ta luôn tìm được một đường tăng luồng hoặc một đường luân phiên như vậy. Bạn đọc có thể tự chứng minh tính đúng đắn của nhận định này. Để cài đặt, ta chỉ cần thêm vào một điều kiện dừng khi đỉnh kết thúc của quá trình dfs là đỉnh chưa được ghép hoặc đỉnh đã được ghép nhưng không thuộc ~R~.

Các bạn có thể tham khảo code đầy đủ ở bên dưới (lưu ý code có sử dụng tính năng C++17):

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 200 + 2;

int m, n;
char tab[N][N];
int match[N];
vector<int> g[N];
int vst[N];
int res[N][N];

bool dfs(int u, int tme, int t)
{
    if (vst[u] == tme) return false;
    vst[u] = tme;

    for (int v : g[u])
        if (bool right_reassign = u > m && g[match[v]].size() < t; !match[v] || right_reassign || dfs(match[v], tme, t)) {
            if (right_reassign)
                match[match[v]] = 0;
            match[u] = v;
            match[v] = u;
            return true;
        }

    return false;
}

int main()
{
    cin >> m >> n;

    for (int i = 1; i <= m; ++i) cin >> tab[i] + 1;

    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            if (tab[i][j] == '1') {
                int u = i, v = j + m;
                g[u].push_back(v);
                g[v].push_back(u);
            }

    int p = 0;
    for (int i = 1; i <= m + n; ++i)
        p = max(p, (int) g[i].size());

    cout << p << '\n';

    int tme = 0;
    for (int t = p; t >= 1; --t) {
        fill(match + 1, match + 1 + m + n, false);
        for (int i = 1; i <= m + n; ++i)
            if (g[i].size() == t && !match[i])
                dfs(i, ++tme, t);

        for (int u = 1; u <= m; ++u)
            if (int v = match[u]; v != 0) {
                res[u][v - m] = t;
                g[u].erase(find(g[u].begin(), g[u].end(), v));
                g[v].erase(find(g[v].begin(), g[v].end(), u));
            }
    }

    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            cout << res[i][j] << " \n"[j == n];
    return 0;
}

Cho ~m = n~, độ phức tạp của code trên là ~O(n^4)~ vì ta tìm ~O(n^2)~ đường tăng luồng/luân phiên, mỗi lần mất ~O(n^2)~, tuy nhiên vẫn chạy rất nhanh (0.01s trên VNOJ) vì đây là cặp ghép.

Lời giải 2

Lời giải sau thiên về thuật toán hơn. Bạn nên đọc chậm rãi, và vẽ hình ra để dễ hình dung.

Ta lần lượt thêm các cạnh ~(x, y)~ vào đồ thị. Với mỗi đỉnh, ta có thể tìm được một màu chưa dùng, lần lượt gọi là ~cx~ và ~cy~. Dễ thấy màu này luôn tồn tại vì số màu bằng bậc của đỉnh tối đa.

Nếu ~cx = cy~, ta đơn giản là thêm vào cạnh với màu này.

Nếu ~cx \neq cy~, ta sẽ làm như sau. Ta muốn thêm cạnh ~(x, y)~ với màu ~cx~. Tuy nhiên, đỉnh ~y~ có một cạnh có màu ~cx~. Vậy, ta sẽ đổi cạnh có màu ~cx~ này thành màu ~cy~. Gọi đầu mút không phải ~v~ của cạnh này là ~w~.

• Nếu ~w~ không kề cạnh nào có màu ~cy~, coi như ta xong.
• Ngược lại, ~w~ kề cạnh có màu ~cy~, ta lại đổi nó thành màu ~cx~, xong tiếp tục quá trình.

Từ quan sát trên, ta dẫn tới ý tưởng như sau: Từ ~y~, ta tìm một đường luân phiên giữa màu ~cx~ và màu ~cy~. Đường luân phiên này là một đường đơn, có nghĩa là không có đỉnh nào lặp lại 2 lần. Chứng minh: nếu có đỉnh lặp lại 2 lần, đỉnh đó sẽ có bậc > 2, tuy nhiên ta chỉ có 2 màu, vì vậy sẽ có 2 cạnh cùng màu, một điều vô lý vì đồ thị của chúng ta đang đúng. Đường luân phiên này cũng không thể kết thúc tại ~y~, vì nếu kết thúc tại ~y~, suy ra ~y~ có màu ~cy~, trái với giả thiết ban đầu. Đường này cũng không chứa đỉnh ~x~ vì lý do tương tự. Đường này có độ dài hữu hạn vì đồ thị của chúng ta có hữu hạn đỉnh.

Sau khi tìm được đường luân phiên này, ta đảo ngược màu của tất cả các cạnh, từ ~cx~ thành ~cy~ và ngược lại. Khi đó, ta sẽ có đỉnh ~y~ sẽ không còn có cạnh kề màu ~cx~ nữa, vì vậy ta có thể thêm cạnh ~(x, y)~ có màu ~cx~.

Các bạn có thể tham khảo code đầy đủ bên dưới:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 200 + 2;

int m, n, p;
char tab[N][N];
int match[N][N];
int deg[N];
int res[N][N];

void color(int x, int y)
{
    int cx = find(match[x] + 1, match[x] + 1 + p, 0) - match[x];    // find free color
    int cy = find(match[y] + 1, match[y] + 1 + p, 0) - match[y];

    if (cx != cy)
        for (int u = y, c = cx, v = match[u][c]; v; c = cx + cy - c) {
            int invc = cx + cy - c;
            int tmp = match[v][invc];

            match[u][invc] = v;
            match[v][invc] = u;

            u = v, v = tmp;
            if (!v)
                match[u][c] = 0;
        }
    match[x][cx] = y;
    match[y][cx] = x;
}

int main()
{
    cin >> m >> n;

    for (int i = 1; i <= m; ++i) cin >> tab[i] + 1;

    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            if (tab[i][j] == '1') {
                int u = i, v = j + m;
                ++deg[u], ++deg[v];
            }

    p = *max_element(deg + 1, deg + 1 + m + n);
    cout << p << '\n';

    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            if (tab[i][j] == '1')
                color(i, j + m);

    for (int u = 1; u <= m; ++u)
        for (int c = 1; c <= p; ++c)
            if (int v = match[u][c]; match[u][c])
                res[u][v - m] = c;

    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            cout << res[i][j] << " \n"[j == n];
    return 0;
}

Độ phức tạp của lời giải trên là ~O(n^3)~, do mỗi dường luân phiên có thể tìm trong ~O(n)~.