Luogu P6967 Delight for a Cat

比较重要的区间限制建网络流方法，以前没有见过，记录一下。

题意：构造一个长度为 $n$ 的 01 序列，每个点选 01 分别有一些权值，并且每长度为 $k$ 的至少有 $m_0$ 个 0，$m_1$ 个 1。问最大权值。$n\leq 1000$。

做法来自 ix35，在这里表示感谢。

考虑以下的模型：给定 $m$ 个在 $[1, n]$ 的区间，每个区间代价为 $w$，最多选 $f$ 次，最后每个点的覆盖次数满足一个区间限制，求最小代价。

建出一个链的图，如下，我们暂且用 $i\to i + 1$ 的流量刻画 $i$ 的覆盖次数：

我们把 $[l, r]$ 的一次覆盖记作 $l$ 节点向 $r + 1$ 节点流 1 的流量，那么 $[l, r]$ 本身的流量就减少一。那么我们可以使用减少的流量来刻画覆盖次数，于是我们要求 $i\to i + 1$ 的边有上下界。假设范围为 $[l_i, r_i]$ 表示 $i$ 的覆盖范围，那么我们先给足够的流量 $M$，然后设置 $i\to i + 1$ 的流量 $\in[M - r_i, M - l_i]$。在有些题目中所有的 $r_i$ 相同，于是我们可以把 $M$ 设置为共同的 $r_i$，就没有下界，于是变为了普通的费用流。

在这个题中，我们用 $i$ 节点表示 $[i, i + k - 1]$ 的区间的 1 的个数，容易发现他的流量有一个上下界。然后覆盖某一位置时，他所影响的位置容易表示为一个区间。这道题目属于我们刚刚说的所有上界相同，于是无需上下界费用流，直接跑即可。输出方案直接在加边的时候记录当前编号，最后看一下流量即可。

int main()
{
	// [mb, k - ma]
	int n, k, ma, mb;
	std::cin >> n >> k >> ma >> mb;
	if (ma + mb > k) return puts("0"), 0;
	std::vector<int> a(n), b(n), id(n);
	for (int &x : a) scanf("%d", &x);
	for (int &x : b) scanf("%d", &x);
	LL sum = 0;
	for (int &x : a) sum += x;
	MCMFGraph<int, LL> mcmf(n - k + 2, n * 5);
	mcmf.S = n - k + 2, mcmf.T = n - k + 1;
	mcmf.add(n - k + 2, 0, k - ma, 0);
	for (int i = 0; i < n; ++ i)
		id[i] = mcmf.idx, mcmf.add(std::max(i - k + 1, 0), std::min(n - k, i) + 1, 1, b[i] - a[i]);
	for (int i = 0; i <= n - k; ++ i) mcmf.add(i, i + 1, k - mb - ma, 0);
	std::cout << sum + mcmf.solve().second << std::endl;
	LL cur = 0;
	for (int x = 0; x < n; ++ x)
	{
		int i = id[x];
		putchar(mcmf.edg[i].f ? 'S' : 'E');
		cur += !mcmf.edg[i].f * (b[x] - a[x]);
	}
	// std::cout << '\n' << cur << std::endl;
	return 0;
}