题目
题意
有 $n$ 个文件，其中有 $k$ 个必须上传，其他所有文件不可以上传。
每次上传操作可以选择按照文件名字典序排序或按照创建时间排序，然后上传一段连续区间里的所有文件。
题解
考虑最小割。
假设现在以字典序排序或按照创建时间排序。一个需要上传的文件如果不和 该排序下的下一个文件 一起上传，那么就需要耗费额外的 $1$ 的代价。在网络图上的表示即为 $i$ 和 $i + 1$ 连一条流量为 $1$ 的边。如果没有该排序下的下一个文件，或者该排序下的下一个文件不可以上传，就说明这个代价一定得花，可以直接向汇点连一条流量为 $1$ 的边。
两个排序下都这样建边后可以直接跑最小割了。
代码
void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
tp n, k; bin >> n >> k;
vector<vector<PTT>> e(n + 2);
vector<bool> upl(n + 2, false);
while (k--) upl[bin] = true;
vector<tp> a(n + 2), b = a;
for (tp i = 1; i <= n; ++i) b[a[i] = bin] = i;
a[n + 1] = n + 1;
for (tp i = 1; i <= n; ++i) {
if (!upl[i]) continue;
if (upl[i + 1]) e[i].emplace_back(i + 1, 1);
else e[i].emplace_back(n + 1, 1);
if (upl[a[b[i] + 1]]) e[a[b[i] + 1]].emplace_back(i, 1);
else e[0].emplace_back(i, 1);
}
bin << lib::Max_Flow(e, 0, n + 1) << '\n';
}
void MIST() {
}