给定一个 $N$ 行 $M$ 列的方格表，每个小方格中都有一个数，所有的数恰好构成 $1 \sim N M$ 的一个排列。记第 $i$ 行第 $j$ 列的数为 $A_{i, j}$。
你需要通过下面三种操作将方格表中的数重新排列：
当然，你希望在重排完成后，第 $i$ 行第 $j$ 列的数恰好是 $M \times \left( i - 1 \right) + j$。
你需要输出一组方案，可以证明一定存在可行的方案。
第一行包含两个正整数 $N, M$ ($N, M \leq 100$)，表示方格表的行数和列数。
接下来 $N$ 行，每行 $M$ 个正整数 $A_{i, j}$ ($1 \leq A_{i, j} \leq N M$)，描述这个方格表。保证所有 $A_{i, j}$ 构成 $1 \sim N M$ 的一个排列。
输出 $2 N$ 行，每行 $M$ 个整数。前 $N$ 行表示第 1 步完成后的方格表，后 $N$ 行表示第 2 步完成后的方格表，具体格式同输入格式。
注意到前后都有 "行操作"，因此我们不妨把每一行的元素看成一个 (无序的) 集合。
我们对两个方格表中的每行指定一种颜色，比如第 $i$ 行的颜色为 $c_i$，将其染为对应的颜色。于是，我们容易求出每个数的起始颜色和最终颜色。
那么考虑第二次操作的每一列，相当于原先的 $N$ 个元素，它们的颜色是 $c_1, c_2, \cdots, c_N$ 的排列，而将它们重排后，颜色仍为 $c_1, c_2, \cdots, c_N$ 的排列。
也就是说，对于每一列，我们都需要在当前剩下的数中寻找 $N$ 个，使得它们的起始颜色和最终颜色分别形成 $c_1, c_2, \cdots, c_N$ 的排列。
如果你们对这种排列问题比较敏感，立马可以发现这就是一个经典的二分图匹配模型。
我们在两部各建立 $N$ 个点，分别表示起始颜色点 $u_i$ 和最终颜色点 $v_i$。
然后对于一个数 $t$，设它的起始颜色为 $A$，最终颜色为 $B$ (注意这是已知的)，我们在 $u_A$ 和 $v_B$ 之间连接一条边，这条边就表示数 $t$。
于是，每一列的 $N$ 个数就对应到这个二分图的一个完美匹配 ($1-$因子)。
考虑整张二分图，它每一部均有 $N$ 个点，共有 $N M$ 条边，我们需要找到它的 $M$ 个完美匹配 ($1-$因子)。换句话说，我们就需要找到这张二分图的一个 $1-$因子分解。
那它是否有 $1-$因子分解呢？考虑每个点的度数，对于左部的一个点 $u_i$，它的每一条出边都表示第 $i$ 行的一个数，因此它共有 $M$ 条出边 $\Rightarrow \deg \left( u_i \right) = M$。于是，每个点的度数均为 $M$，从而二分图是 $M-$正则二分图。
由 Hall 定理推论可知，正则二分图一定存在 $1-$因子分解。于是，我们只需要暴力通过匈牙利算法找到 $M$ 组匹配，输出即可。
时间复杂度 $O \left( N^2 M^2 \right)$ (当然可以通过网络流或其它 $1-$因子分解算法达到 $O \left( N^{3/2} M^2 \right)$ 或者 $O \left( N^2 M \right)$)。
#include <bits/stdc++.h>
#define EB emplace_back
typedef std::pair <int, int> pr;
typedef std::vector <pr> vecpr;
const int N = 108, N2 = 10054;
int R, C;
int A1[N2], A2[N2], ans1[N][N], ans2[N][N];
int matL[N], matR[N];
bool used[N];
vecpr G[N];
bool dfs(int x) {
int y;
for (const pr &p : G[x])
if (!used[y = p.first])
if (used[y] = true, !~matL[y] || dfs(matL[y]))
return matL[y] = x, matR[x] = y, true;
return false;
}
int main() {
int i, j, x, n, match;
scanf("%d%d", &R, &C);
for (i = 0; i < R; ++i) {
for (j = 0; j < C; ++j) scanf("%d", &x), A1[--x] = i;
std::fill(A2 + i * C, A2 + (i + 1) * C, i);
}
for (i = 0; i < R * C; ++i) G[ A1[i] ].EB(A2[i], i + 1);
for (match = 0; match < C; ++match) {
memset(matL, -1, R << 2), memset(matR, -1, R << 2);
for (i = 0; i < R; ++i) memset(used, false, R), assert( dfs(i) );
for (i = 0; i < R; ++i)
for (n = G[i].size(), j = 0; j < n; ++j)
if (G[i][j].first == matR[i]) {
ans1[i][match] = ans2[ matR[i] ][match] = G[i][j].second;
G[i].erase(G[i].begin() + j); break;
}
}
for (i = 0; i < R; ++i) for (j = 0; j < C; ++j) printf("%d%c", ans1[i][j], j == C - 1 ? 10 : 32);
for (i = 0; i < R; ++i) for (j = 0; j < C; ++j) printf("%d%c", ans2[i][j], j == C - 1 ? 10 : 32);
return 0;
}
坑1：二分图匹配 (匈牙利算法) 的时候注意 used[] 数组清空的时间，以保证复杂度。
坑2：输出时注意格式，不要把行和列搞混了。