Link. 有附加内容。懒得搬了。

最喜欢的一集。

题目的要求十分简洁，但是贡献的计算非常繁琐诡异，而 $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$。答案即为正权点权值和减去最小割。