Hall 定理：对于一个左部点个数不多于右部点个数的二分图 $G$，设 $N(S)$ 代表 $G$ 中与左部点集合 $S$ 中至少一个点有连边的右部点的集合，则 $G$ 存在完美匹配的充分必要条件是，对于任意的非空左部点集合 $S$，总有 $|N(S)| \ge |S|$。

考虑对于一个给定的权值 $t$ 求解最小权值能够不小于它的最小 $k$ 值。

则对于任意的非空左部点集合 $S$，无论哪 $m - k$ 个右部点被删去，最终的二分图都要有 $|N(S)| \ge |S|$，因此原图中 $|N(S)| \ge |S| + m - k$，即 $k \ge |S| - |N(S)| + m$。

根据 Hall 定理，对所有 $2^n - 1$ 个集合 $S$ 分别计算 $|S| - |N(S)| + m$，取其中的最大值即可得到确保能够完成归还工作的最小 $k$ 值。

考虑倒序枚举 $t = nm, nm - 1, \ldots, 1$，每次会有若干个 $|N(S)|$ 的值减少 $1$（$nm$ 轮中一共会有 $(2^n - 1) \cdot m$ 次减少操作）。由于 $|S| - |N(S)| + m$ 的值总是不大于 $n + m$ 且随枚举过程单调递增，结合双指针开桶统计 $|S| + |N(S)| - m$ 的分布情况即可实现 $O(1)$ 单点修改和 $O(1)$ 查询最大值。

最终的时间复杂度为 $O(2^n \cdot m)$，空间复杂度为 $O(nm + 2^n)$。

（std 中对 $d_{i, j}$ 使用了 std::sort，导致实际的时间复杂度为 $O(2^n \cdot m + nm \log nm)$。由于题目保证了矩阵 $\{d_{n, m}\}$ 中的所有元素构成一个 $\{1, 2, \ldots, nm\}$ 的排列，这一点可以使用桶排序来规避。）

#include <bits/stdc++.h>
using namespace std;
const int N = 10 + 2;
const int M = 1e5 + 12;
const int D = 1 << N;
const int S = N + M;
const int T = N * M;
int b[D], e[M], t[S];
struct I
{
	int i;
	int j;
	int v;
};
I d[T];
bool cmp(I x, I y)
{
	return x.v < y.v;
}
inline int lowbit(int x)
{
	return x & (-x);
}
inline int popcount(int x)
{
	int c = 0;
	while (x)
	{
		c++;
		x -= lowbit(x);
	}
	return c;
}
int main()
{
	freopen("brooms.in", "r", stdin);
	freopen("brooms.out", "w", stdout); 
	int n, m, p, l = 0;
	scanf("%d %d", &n, &m);
	p = m - 1;
	for (int i = 1; i < (1 << n); i++)
		b[i] = m + n - popcount(i);
	for (int i = 1; i < (1 << n); i++)
		t[b[i]]++;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			l++;
			scanf("%d", &d[l].v);
			d[l].i = i - 1;
			d[l].j = j;
		}
	sort(d + 1, d + l + 1, cmp);
	for (int i = l; i >= 1; i--)
	{
		int s = d[i].j, j = e[s];
		do
		{
			int o = (1 << d[i].i) | j;
			t[b[o]]--;
			b[o]--;
			t[b[o]]++;
			j = (j - 1) & e[s];
		}
		while (j != e[s]);
		e[s] |= 1 << d[i].i;
		while (t[p])
		{
			printf("%d", d[i].v);
			if (p == n - 1)
			{
				puts("");
				return 0;
			}
			putchar(' ');
			p--;
		}
	}
	return 0;
}