【AtCoder Grand 037D】Sorting a Grid 题解

题目大意

  给定一个 $n$ 行 $m$ 列的矩阵，里面的元素是 $1,\cdots,nm$ 每个恰好出现一次。依次执行以下操作：

1. 对每一行任意重排；
2. 对每一列任意重排；
3. 对每一行任意重排，

使得最后矩阵第 $i$ 行第 $j$ 列恰好是 $i(m-1)+j$。输出一种方案（第 1 步和第 2 步后的结果）。可证明一定有解。

  $n, m \le 100$
  2s

$$\\$$ $$\\$$ $$\\$$

题解

  一些简单的推导：把一个元素属于第几行（即除以 $m$ 上取整）叫做它的颜色。第 3 步对每一行重排，因此第 2 步结束后肯定是每个元素都去到了它所在的行，这时候每一列包含每种颜色恰好一个，这也是第 1 步要达成的效果。因此问题变成：每行重排，使得每列包含每种颜色恰好一个。
  这时候就能嗅到匹配的味道了，但具体怎么匹配还是有点技巧。
  题解给的做法是一列一列确定。建一个二分图，左边 $n$ 个点表示行，右边 $n$ 个点表示颜色，连边表示这一行有这种颜色。这个二分图是有完美匹配的（证明：Hall 定理，任取左边若干个点，它连向右边的点表示选取的行总共包含了多少种颜色，这不可能比行数少，不然就有颜色超过 $m$ 个了），把这个完美匹配拉出来作为第 1 列，剩下的变成 $(n,m-1)$ 的子问题了，因此总共做 $m$ 次二分图匹配就好了。

  官方题解给的有完美匹配的证明似乎有点问题，它说二分图每个点的度数都是 $m$ 因此符合 Hall 定理，但这“度数为 $m$”是有重边的，不能直接应用 Hall 定理。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

const int maxn=105;

int n,m,a[maxn][maxn],b[maxn][maxn],br[maxn][maxn],c[maxn];
vector<int> e[maxn];

inline int getr(const int &x) {return (x+m-1)/m;}

int f[maxn],bz[maxn];
bool Hung(int k,int tim) {
	if (bz[k]==tim) return 0;
	bz[k]=tim;
	for(int go:e[k]) if (!f[go] || Hung(f[go],tim)) {
		f[go]=k;
		return 1;
	}
	return 0;
}

int main() {
	scanf("%d %d",&n,&m);
	fo(i,1,n) {
		fo(j,1,m) scanf("%d",&a[i][j]);
		sort(a[i]+1,a[i]+1+m);
	}
	
	int tm=0;
	fo(j,1,m) {
		fo(i,1,n) e[i].clear();
		fo(i,1,n)
			fo(k,j,m) if (k==j || getr(a[i][k])!=getr(a[i][k-1])) {
				int r=getr(a[i][k]);
				e[i].push_back(r);
				br[i][r]=k;
			}
		
		memset(f,0,sizeof(f));
		fo(i,1,n) Hung(i,++tm);
		
		fo(i,1,n) {
			int ii=f[i];
			b[ii][j]=a[ii][br[ii][i]];
			a[ii][br[ii][i]]=-1;
			sort(a[ii]+1,a[ii]+1+m);
		}
	}
	fo(i,1,n) {
		fo(j,1,m) printf("%d ",b[i][j]);
		putchar('\n');
	}
	
	fo(j,1,m) {
		fo(i,1,n) c[i]=b[i][j];
		sort(c+1,c+1+n);
		fo(i,1,n) b[i][j]=c[i];
	}
	fo(i,1,n) {
		fo(j,1,m) printf("%d ",b[i][j]);
		putchar('\n');
	}
}