问题描述
Kiana 最近喜欢到一家非常美味的寿司餐厅用餐。
每天晚上，这家餐厅都会按顺序提供 (n) 种寿司，第 (i) 种寿司有一个代号 (a_i) 和美味度 (d_{i, i})，不同种类的寿司有可能使用相同的代号。每种寿司的份数都是无限的，Kiana 也可以无限次取寿司来吃，但每种寿司每次只能取一份，且每次取走的寿司必须是按餐厅提供寿司的顺序连续的一段，即 Kiana 可以一次取走第 (1, 2) 种寿司各一份，也可以一次取走第 (2, 3) 种寿司各一份，但不可以一次取走第 (1, 3) 种寿司。
由于餐厅提供的寿司种类繁多，而不同种类的寿司之间相互会有影响：三文鱼寿司和鱿鱼寿司一起吃或许会很棒，但和水果寿司一起吃就可能会肚子痛。因此，Kiana 定义了一个综合美味度 (d_{i, j} (i < j))，表示在一次取的寿司中，如果包含了餐厅提供的从第 (i) 份到第 (j) 份的所有寿司，吃掉这次取的所有寿司后将获得的额外美味度。由于取寿司需要花费一些时间，所以我们认为分两次取来的寿司之间相互不会影响。注意在吃一次取的寿司时，不止一个综合美味度会被累加，比如若 Kiana 一次取走了第 (1, 2, 3) 种寿司各一份，除了 (d_{1, 3}) 以外，(d_{1, 2}, d_{2, 3}) 也会被累加进总美味度中。
神奇的是，Kiana 的美食评判标准是有记忆性的，无论是单种寿司的美味度，还是多种寿司组合起来的综合美味度，在计入 Kiana 的总美味度时都只会被累加一次。比如，若 Kiana 某一次取走了第 (1, 2) 种寿司各一份，另一次取走了第 (2, 3) 种寿司各一份，那么这两次取寿司的总美味度为 (d_{1, 1} + d_{2, 2} + d_{3, 3} + d_{1, 2} + d_{2, 3})，其中 (d_{2, 2}) 只会计算一次。
奇怪的是，这家寿司餐厅的收费标准很不同寻常。具体来说，如果 Kiana 一共吃过了 (c (c > 0)) 种代号为 (x) 的寿司，则她需要为这些寿司付出 (mx^2 + cx) 元钱，其中 (m) 是餐厅给出的一个常数。
现在 Kiana 想知道，在这家餐厅吃寿司，自己能获得的总美味度（包括所有吃掉的单种寿司的美味度和所有被累加的综合美味度）减去花费的总钱数的最大值是多少。由于她不会算，所以希望由你告诉她。
题解
模型，最大权闭合子图。
有 (n) 个物品，第 (i) 个物品的价值为 (w_i)（可以为负），存在若干形如选 (i) 必须选 (j) 的限制。
最小割。
令超源 (S) 所在的集合为选择的物品集合，超汇 (T) 所在的集合为不选择的物品的集合，显然对于一个物品 (i) ，要么属于 (S) ，要么属于 (T)。
令 (sum = sumlimits_{w_i>0}{w_i})
对于价值为正的物品 (i)，从 (S) 向 (i) 连边，边权为 (w_i)，表示不选择 (i) 会损失 (w_i) 的收益。
对于价值为负或零的物品 (i)，从 (i) 向 (T) 连边，边权为 (-w_i) （显然 (-w_i > 0) ），表示选择了 (i) 要付出 (-w_i) 的代价，即损失 (-w_i) 的收益。
对于选择 (i) 必选 (j) 的限制，由 (i) 向 (j) 连边，表示 (j) 必须属于 (i) 所在的集合。
设最小割为 (ans)，则最后所选择物品的收益最大值为 (sum - ans) 。
( exttt{---------------------------------------------------------------------------------})
对于本题，将每个 (d_{i,j}) 视作一个物品。
特别地，新建 (max{a_i}) 个点，表示代号。
对于代号点，向 (T) 连 (m imes a_i^2) 的边，表示选择过这代号的寿司的代价。
对于寿司点，即 (d_{i,i}) 点，向 (T) 连 (a_i) 的边，表示选择其所付出的价格；向对应代号点连边，表示选取这个寿司后一定会启用这个代号。
若选择 (d_{i,j}) ，必选 (d_{i + 1,j},d_{i,j-1})。
再按照最大权闭合子图建图就好了。
( exttt{Code})
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100 + 7;
const int maxnode = 7000 + 7;
const int maxm = 5000000 + 7;
const int INF = 0x3f3f3f3f;
int n, m, tot = 1, S = 7000, T = 7001;
int a[maxn];
int Head[maxnode], to[maxm], Next[maxm], w[maxm];
void addedge(int x, int y, int z) {
to[++tot] = y, Next[tot] = Head[x], Head[x] = tot, w[tot] = z;
}
void add(int x, int y, int z) {
addedge(x, y, z);
addedge(y, x, 0);
}
int id(int x, int y) {
return (n * 2 - x + 2) * (x - 1) / 2 + y - x + 1;
}
int aimax;
int d[maxn][maxn];
void Init(void) {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
aimax = max(aimax, a[i]);
}
for(int i = 1; i <= n; i++) {
for(int j = i; j <= n; j++) {
scanf("%d", &d[i][j]);
}
}
}
int ans;
/*
------------------- id defination -------------------
Range [1, (n + 1) * n / 2] FOR all d_{i,j}
Point (2 * n + 2 - i) * (i - 1) / 2 + j FOR d_{i,j}
Range [(n + 1) * n / 2 + 1, (n + 1) * n / 2 + max{a_i} ] FOR all a_i
Point (n + 1) * n / 2 + i FOR a_i
Point 7000 FOR S
Point 7001 FOR T
*/
void Graph_Build(void) {
for(int i = 1; i <= aimax; i++) {
add((n + 1) * n / 2 + i, T, m * i * i);
}
for(int i = 1; i <= n; i++) {
for(int j = i; j <= n; j++) {
if(d[i][j] > 0) {
ans += d[i][j];
add(S, id(i, j), d[i][j]);
}
else {
add(id(i, j), T, -d[i][j]);
}
}
add(id(i, i), T, a[i]);
add(id(i, i), (n + 1) * n / 2 + a[i], INF);
}
for(int i = 1; i <= n; i++) {
for(int j = i + 1; j <= n; j++) {
int x = i, y = j - 1;
if(x <= y) add(id(i, j), id(x, y), INF);
x = i + 1, y = j;
if(x <= y) add(id(i, j), id(x, y), INF);
}
}
}
int D[maxnode];
bool bfs(void) {
memset(D, 0, sizeof(D));
queue < int > q;
q.push(S); D[S] = 1;
while(q.size()) {
int x = q.front(); q.pop();
for(int i = Head[x]; i; i = Next[i]) {
int y = to[i];
if(D[y] || !w[i]) continue;
D[y] = D[x] + 1; q.push(y);
if(y == T) return true;
}
}
return false;
}
int dfs(int x, int flow) {
if(x == T) return flow;
int rest = flow;
for(int i = Head[x]; i && rest; i = Next[i]) {
int y = to[i];
if(D[y] != D[x] + 1 || !w[i]) continue;
int k = dfs(y, min(rest, w[i]));
if(!k) D[y] = 0;
else w[i] -= k, w[i ^ 1] += k, rest -= k;
}
return flow - rest;
}
int sum;
void Dinic(void) {
int t;
while(bfs()) {
while(t = dfs(S, INF)) sum += t;
}
}
void debug() {
for(int i = 2; i <= tot; i += 2) {
printf("%d %d %d
", to[i ^ 1], to[i], w[i]);
}
}
void Work(void) {
Graph_Build();
// debug();
Dinic();
printf("%d
", ans - sum);
}
int main(void) {
Init();
Work();
return 0;
}