自动搬运

查看原文

来自洛谷，原作者为

	小粉兔 Always continue; Never break;

搬运于2025-08-24 21:52:19，当前版本为作者最后更新于2019-02-23 15:38:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

在博客园食用更佳：https://www.cnblogs.com/PinkRabbit/p/10422815.html。

题意简述：

有 $n$ 种寿司，第 $i$ 种寿司的类型为 $a_i$。

如果你吃了第 $i$ 种到第 $j$ 种寿司，你会得到 $d_{i,j}$（$i\le j$）的收益。

如果你吃了 $c$（$c>0$）种类型为 $x$ 的寿司，你会付出 $mx^2+cx$ 的代价（$m\in\{0,1\}$）。

最大化收益与代价的差。

题解：

一种经典的模型：最大权闭合子图。

模型：有若干个物品，每种物品有一个可正可负的价值 $v_i$，选取了物品就意味着获得了价值。

物品之间有限制关系：$x\to y$ 表示若要选择物品 $x$ 则必须选择物品 $y$。

目标是最大化价值和。

显然，有时需要为了一个拥有较大价值的物品而被迫选择负价值的物品。

考虑使用最小割解决此类问题：

将每个物品与源 $S$ 汇 $T$ 相连。若割掉与 $S$ 相连的边表示不选这个物品，割掉与 $T$ 相连的边表示选择这个物品。

对于一个物品的价值 $v$，如果 $v>0$ 则令它与 $S$ 相连的边的权值为 $v$，与 $T$ 相连的边的权值为 $0$，将 $v$ 加入答案。表示不选择这个物品会付出 $v$ 的代价；
如果 $v<0$ 则令它与 $S$ 相连的边的权值为 $0$，与 $T$ 相连的边的权值为 $-v$（显然 $-v>0$）。表示选择这个物品会付出 $-v$ 的代价。

对于 $x\to y$ 的关系，转化为 $x$ 向 $y$ 连一条权值为 $\infty$ 的边，显然这条边永远不会被割，如果选择了 $x$，即割掉 $x$ 与 $T$ 相连的边，那么如果不选 $y$，即割掉 $y$ 与 $S$ 相连的边，就会出现路径 $S\to x\to y\to T$，所以必须选择 $y$。而如果不选 $x$ 则对 $y$ 的选择没有影响。

因为权值全部为非负数，符合使用 Dinic 算法解决网络流的条件，结合最大流最小割定理，可以使用 Dinic 算法解决此类问题。

回到题目上来，我们将每种 $d_{i,j}$ 的收益都看做一个物品。显然如果选择 $d_{i,j}$（$i<j$），则必须选择 $d_{i,j-1}$ 以及 $d_{i+1,j}$。

而如果吃了 $c$（$c>0$）种类型为 $x$ 的寿司，需要付出 $mx^2+cx$ 的代价。
这可以转化为：吃了每种类型为 $x$ 的寿司需要付出 $x$ 的代价，而吃过类型为 $x$ 的寿司需要付出 $mx^2$ 的代价。

选择了 $d_{i,i}$ 就代表吃掉了第 $i$ 种寿司，这时需要付出 $a_i$ 的代价（$a_i$ 是这种寿司的类型）。

选择了 $d_{i,i}$ 还意味着：必须付出 $m\cdot a_i^2$ 的代价，我们将每个寿司类型也看作一个物品，选择收益 $d_{i,i}$ 则必须选择类型 $a_i$。

至此，所有限制都转化为了“选择 $x$ 则必须选择 $y$”的形式，可以使用最大权闭合子图的模型解决了。

在代码中，$S$、$T$ 分别是 $1$ 和 $2$ 号点，$d_{i,j}$ 是 $\mathrm{Id}[i][j]$ 号点，接下来的点则是每种寿司类型。

#include <cstdio>
#include <cstring>
#include <algorithm>

typedef long long LL;
const LL Inf = 0x7fffffffffffffff;

namespace DinicFlow {
	const int MN = 6060, MM = 16055;
	
	int N, S, T;
	int h[MN], iter[MN], nxt[MM * 2], to[MM * 2], tot = 1; LL w[MM * 2];
	inline void ins(int u, int v, LL x) { nxt[++tot] = h[u], to[tot] = v, w[tot] = x, h[u] = tot; }
	inline void insw(int u, int v, LL x) { ins(u, v, x); ins(v, u, 0); }
	
	int lv[MN], que[MN], l, r;
	
	inline bool Lvl() {
		memset(lv, 0, sizeof(lv));
		lv[S] = 1;
		que[l = r = 1] = S;
		while (l <= r) {
			int u = que[l++];
			for (int i = h[u]; i; i = nxt[i]) if (w[i] && !lv[to[i]]) {
				lv[to[i]] = lv[u] + 1;
				que[++r] = to[i];
			}
		}
		return lv[T] != 0;
	}
	
	LL Flow(int u, LL f) {
		if (u == T) return f;
		LL d = 0, s = 0;
		for (int &i = iter[u]; i; i = nxt[i]) if (w[i] && lv[to[i]] == lv[u] + 1) {
			d = Flow(to[i], std::min(f, w[i]));
			f -= d, s += d;
			w[i] -= d, w[i ^ 1] += d;
			if (!f) break;
		}
		return s;
	}
	
	inline LL Dinic() {
		LL Ans = 0;
		while (Lvl()) {
			memcpy(iter + 1, h + 1, N * sizeof(h[0]));
			Ans += Flow(S, Inf);
		}
		return Ans;
	}
}

const int MN = 105;

int N, M, A[MN], MxA;
int F[MN][MN], Id[MN][MN], cnt;
LL Ans = 0;

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= N; ++i) scanf("%d", &A[i]), MxA = std::max(MxA, A[i]);
	DinicFlow::S = 1, DinicFlow::T = 2;
	cnt = 2;
	for (int i = 1; i <= N; ++i) for (int j = i; j <= N; ++j) {
		scanf("%d", &F[i][j]), Id[i][j] = ++cnt;
	}
	for (int i = 1; i <= N; ++i) for (int j = i; j <= N; ++j) {
		int cost = F[i][j];
		if (i == j) {
			if (M) DinicFlow::insw(Id[i][j], cnt + A[i], Inf);
			cost -= A[i];
		}
		else {
			DinicFlow::insw(Id[i][j], Id[i + 1][j], Inf);
			DinicFlow::insw(Id[i][j], Id[i][j - 1], Inf);
		}
		if (cost > 0) DinicFlow::insw(1, Id[i][j], cost), Ans += cost;
		if (cost < 0) DinicFlow::insw(Id[i][j], 2, -cost);
	}
	if (M) for (int i = 1; i <= MxA; ++i) DinicFlow::insw(++cnt, 2, i * i);
	DinicFlow::N = cnt;
	printf("%lld\n", Ans - DinicFlow::Dinic());
	return 0;
}