給出一個 $n\times n$ 的矩陣 $A$，你可以進行下述操作任意多次：指定整數 $k$（$1\le k\le n$），使 $A_{ni}$ 與 $A_{in}$ 交換。求你能得到的字典序最小的矩陣大小。

題意

給出一個 \(n\times n\) 的矩陣 \(A\)，你可以進行下述操作任意多次：指定整數 \(k\)（\(1\le k\le n\)），使 \(A_{ni}\) 與 \(A_{in}\) 交換。

求你能得到的字典序最小的矩陣大小。

\(n\le 1000\)

解析

不難發現操作是可逆的，并且操作的順序并不影響結果。那么我們只需要決定要對哪些 \(k\) 進行操作。不妨定義 bool 變量 \(T_i\)，當 \(T_i=\bold{true}\)，表示要操作 \(k\)，反之不操作 \(k\)。

首先字典序能夠想到貪心，即從左往右、從上往下依次使每個位置上的數盡可能小。那么哪些數可能出現在 \((i,j)\)？可以發現任何調換都是關于主對角線反轉，于是只可能有 \(A_{ij}\) 和 \(A_{ji}\) 出現在 \((i,j)\)。

那么怎樣讓 \(A_{ij}\) 最終在 \((i,j)\) ？顯然只有 \(k=i\) 或 \(k=j\) 對 \((i,j)\) 有影響，稍微推導可以知道結果是 \(T_i=T_j\)。而讓 \(A_{ji}\) 最終在 \((i,j)\) 則要求 \(T_i\neq T_j\)。

那么可以看出這是一個 2-sat 問題。再回到本題的具體解決方法，從上到下從左往右地枚舉右上側的位置（原因即字典序），如果 \(A_{ij}=A_{ji}\)，則沒有任何限制；如果 \(A_{ij}>A_{ji}\) 則要求 \(T_i\neq T_j\)；如果 \(A_{ij}< A_{ji}\) 則要求 \(T_i=T_j\)。

當然可能無法滿足要求，說明無法在不影響先前的位置的前提下使當前位置最小，又根據字典序的性質，此時不能滿足當前位置最小，否則可以滿足。

那怎么判斷 2-sat 問題是否有解？Tarjan？那么邊數以及進行 Tarjan 的次數都是 \(O(n^2)\)，\(O(n^4)\) 顯然不能過。只會添加條件？強連通縮點！然而每次添加條件并不會保證強連通數量嚴格減少，復雜度依然錯誤。

那么此時需要關注條件形式——相等或不等。那么我們可以這樣說，兩個變量之間要么沒有關聯，要么一個變量決定后，另一個變量必然確定。于是延申出下述方案——

把可以確定相等的變量縮點，并且記錄與這個變量不等的變量是哪一個。例如現在有兩個不相干的變量 \(a,b\)（\(a,b\) 分別代表一個縮點），\(a',b'\) 代表與 \(a,b\) 不等的變量。如果現在確定 \(a\neq b\)，則 \(a'=b\)，\(b'=a\)，可以進一步縮點；如果確定 \(a=b\)，則 \(a=b\) 且 \(a'=b'\)。

上面是不相干的變量，如果是相關的變量 \(a,b\)，此時要么合法，不會產生新的縮點，要么不合法。例如，如果有要求 \(a=b\)，而我們發現 \(a'=b\)（準確的說，\(b\) 在 \(a'\) 這個縮點中），此時就發生了矛盾。

最后，怎么縮點？只縮不拆，并查集。

源代碼

#include <cstdio>
#include <cstring>
#include <algorithm>
const int MAXN = 1005;
struct Dsu
{
    int fa[MAXN], dif[MAXN];
    void clear(const int &siz)
    {
        for (int i = 1; i <= siz; ++i)
        {
            fa[i] = i;
            dif[i] = -1;
        }
    }
    int findFa(const int &src)
    {
        return fa[src] == src ? src : fa[src] = findFa(fa[src]);
    }
    int combine(int src, int dst)
    {
        src = findFa(src), dst = findFa(dst);
        return fa[src] = dst;
    }
    void linkSame(int ele_a, int ele_b)
    {
        ele_a = findFa(ele_a), ele_b = findFa(ele_b);
        if (ele_a == ele_b) /* useless */
        {
            return;
        }
        if (ele_a == dif[ele_b]) /* corrupt */
        {
            return;
        }
        int tmp_ele = combine(ele_a, ele_b), tmp_dif = -1;
        if ((~dif[ele_a]) && (~dif[ele_b]))
        {
            tmp_dif = combine(dif[ele_a], dif[ele_b]);
        }
        else
        {
            if (~dif[ele_a])
            {
                tmp_dif = dif[ele_a];
            }
            if (~dif[ele_b])
            {
                tmp_dif = dif[ele_b];
            }
        }
        dif[tmp_ele] = tmp_dif;
        if (~tmp_dif)
        {
            dif[tmp_dif] = tmp_ele;
        }
    }
    void linkDiff(int ele_a, int ele_b)
    {
        ele_a = findFa(ele_a), ele_b = findFa(ele_b);
        if (ele_a == dif[ele_b]) /* useless */
        {
            return;
        }
        if (ele_a == ele_b) /* corrupt */
        {
            return;
        }
        int tmp_ele_a = ele_a, tmp_ele_b = ele_b;
        if (~dif[ele_a])
        {
            tmp_ele_b = combine(tmp_ele_b, dif[ele_a]);
        }
        if (~dif[ele_b])
        {
            tmp_ele_a = combine(tmp_ele_a, dif[ele_b]);
        }
        dif[tmp_ele_a] = tmp_ele_b;
        dif[tmp_ele_b] = tmp_ele_a;
    }
};
Dsu same_block;
int mat[MAXN][MAXN], rev_tag[MAXN];
void doSwap(const int &siz)
{
    same_block.clear(siz);
    for (int rol = 1; rol <= siz; ++rol)
    {
        for (int col = rol + 1; col <= siz; ++col)
        {
            if (mat[rol][col] != mat[col][rol])
            {
                if (mat[rol][col] < mat[col][rol])
                {
                    same_block.linkSame(rol, col);
                }
                else
                {
                    same_block.linkDiff(rol, col);
                }
            }
        }
    }
}
void getAnswer(const int &siz)
{
    std::fill(rev_tag + 1, rev_tag + 1 + siz, -1);
    for (int i = 1; i <= siz; ++i)
    {
        int rt_i = same_block.findFa(i);
        if (rev_tag[rt_i] == -1)
        {
            rev_tag[rt_i] = 1;
            rev_tag[same_block.dif[rt_i]] = 0;
        }
    }
    for (int i = 1; i <= siz; ++i)
    {
        if (rev_tag[same_block.findFa(i)])
        {
            for (int j = 1; j <= siz; ++j)
            {
                std::swap(mat[i][j], mat[j][i]);
            }
        }
    }
}
void solveCase()
{
    int siz;
    scanf("%d", &siz);
    for (int rol = 1; rol <= siz; ++rol)
    {
        for (int col = 1; col <= siz; ++col)
        {
            scanf("%d", &mat[rol][col]);
        }
    }
    doSwap(siz);
    getAnswer(siz);
    for (int rol = 1; rol <= siz; ++rol)
    {
        for (int col = 1; col < siz; ++col)
        {
            printf("%d ", mat[rol][col]);
        }
        printf("%d\n", mat[rol][siz]);
    }
}
int main()
{
    int cnt_case;
    scanf("%d", &cnt_case);
    while (cnt_case--)
    {
        solveCase();
    }
    return 0;
}