https://scg3.piaoztsdy.cn/p/215
Hall 定理：对于一个左部点个数不多于右部点个数的二分图 ，设 代表 中与左部点集合 中至少一个点有连边的右部点的集合，则 存在完美匹配的充分必要条件是，对于任意的非空左部点集合 ，总有 。
考虑对于一个给定的权值 求解最小权值能够不小于它的最小 值。
则对于任意的非空左部点集合 ，无论哪 个右部点被删去，最终的二分图都要有 ，因此原图中 ，即 。
根据 Hall 定理，对所有 个集合 分别计算 ，取其中的最大值即可得到确保能够完成归还工作的最小 值。
考虑倒序枚举 ，每次会有若干个 的值减少 （ 轮中一共会有 次减少操作）。由于 的值总是不大于 且随枚举过程单调递增，结合双指针开桶统计 的分布情况即可实现 单点修改和 查询最大值。
最终的时间复杂度为 ，空间复杂度为 。
（std 中对 使用了 std::sort，导致实际的时间复杂度为 。由于题目保证了矩阵 中的所有元素构成一个 的排列，这一点可以使用桶排序来规避。）
#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;
}
暂无评论