寿司餐厅

ImALAS · 2024-03-20 22:38:00 · 个人记录

最喜欢的一集。

题目的要求十分简洁，但是贡献的计算非常繁琐诡异，而 n 非常小。基本上可以直接放弃别的想法直奔网络流了。

观察一下贡献的形式，发现 d_{i, j} 的贡献方式是我们熟悉的，可以用最大权闭合子图的模型来描述。所以考虑一下最小割。

除了 d_{i, j} 我们还有一个 mx^2 + cx 的贡献。这两个贡献仍然可以看作最大权闭合子图。具体地，选上 d_{i, i} 后会产生 ma_i^2 的代价，如果之前已经产生过了则无所谓。给每种类型建一个点即可。

类似地，cx 可以平摊到每次选 x 的位置上，对 d_{i, i} 对应的 a_i 建立点 A_i 并连边，表示选上 d_{i, i} 则必须选上 -a_i。

然后就没了。讲一下最大权闭合子图，考虑这样一个模型：

给定一张 n 个点 m 条边的有向图。每个点有代价 a_i，可正可负。你可以选上一些点，你的分数是你选的点的 a 之和。但是选点有限制，选上一个点 x 则必须选上 x 能到达的所有点。求最大分数。

这个过程可以看作，选一些正权点，为了得到它们的权值不得不割舍一些负权点的代价。

于是考虑转化一下限制，改写成：选一些正权点，选上一个点后必须选上其所能到达的负权点。

这样做的好处在于，即简化了问题，又保证答案不会改变。感觉非常妙。

然后就是最小割建模。建立源汇点 S, T，对于每个正权点 i，连 S\to i，流量为 a_i。对于每个负权点 i，连 i\to T，流量 -a_i。对于正权点 i 和其所能到达的负权点 j，连边 i\to j，流量 +\infty。答案即为正权点权值和减去最小割。

代码看 这里。挺久之前写的了。

推荐一下 这篇文章。