最大权闭合子图
1.每个区间收益(i,j)对应一个点 权值为正连S 负连T
2.每个区间收益向其子区间收益(i+1,j)与(i,j-1)对应的两个点连边 容量为INF
3.每个寿司类型对应一个点 连一条边到T 容量为m*w[i]*w[i]
4.每个寿司对应的区间收益点(i,i)连一条边到对应的寿司类型 容量为INF 再连一条边到T 容量为w[i]
最后跑最大流
//Netflow dumpling
#include<bits/stdc++.h>
using namespace std;
const int MAXN = ;
const int MAXM = ;
const int INF = ;
int Head[MAXN], cur[MAXN], lev[MAXN], to[MAXM << ], nxt[MAXM << ], f[MAXM << ], ed = , S, T;
inline void addedge(int u, int v, int cap)
{
to[++ed] = v;
nxt[ed] = Head[u];
Head[u] = ed;
f[ed] = cap;
to[++ed] = u;
nxt[ed] = Head[v];
Head[v] = ed;
f[ed] = ;
return;
}
inline bool BFS()
{
int u;
memset(lev, -, sizeof(lev));
queue<int>q;
lev[S] = ;
q.push(S);
while (q.size()) {
u = q.front();
q.pop();
for (int i = Head[u]; i; i = nxt[i])
if (f[i] && lev[to[i]] == -) {
lev[to[i]] = lev[u] + ;
q.push(to[i]);
/*
if (to[i] == T)
{
return 1;
}
magic one way optimize
*/
}
}
memcpy(cur, Head, sizeof Head);
return lev[T] != -;
}
inline int DFS(int u, int maxf)
{
if (u == T || !maxf) {
return maxf;
}
int cnt = ;
for (int &i = cur[u], tem; i; i = nxt[i])
if (f[i] && lev[to[i]] == lev[u] + ) {
tem = DFS(to[i], min(maxf, f[i]));
maxf -= tem;
f[i] -= tem;
f[i ^ ] += tem;
cnt += tem;
if (!maxf) {
break;
}
}
if (!cnt) {
lev[u] = -;
}
return cnt;
}
int Dinic()
{
int ans = ;
while (BFS()) {
ans += DFS(S, );
}
return ans;
}
void init(int SS, int TT)
{
memset(Head, , sizeof(Head));
ed = ;
S = SS;
T = TT;
return;
}
int n, m, now;
bool ok[];
int a[];
int getid(int x, int y)
{
return + n * (x - ) + y;
}
int main()
{
int ans = ;
scanf("%d %d", &n, &m);
S = , T = n * n + ;
for (int i = ; i <= n; i++) {
scanf("%d", &a[i]);
if (!ok[a[i]]) {
addedge(a[i], T, m * a[i]*a[i]), ok[a[i]] = ;
}
addedge(getid(i, i), a[i], INF);
addedge(getid(i, i), T, a[i]);
}
for (int i = ; i <= n; i++) {
for (int j = i; j <= n; j++) {
scanf("%d", &now);
if (now > ) {
addedge(S, getid(i, j), now);
ans += now;
} else {
addedge(getid(i, j), T, -now);
}
if (i != j) {
addedge(getid(i, j), getid(i + , j), INF);
addedge(getid(i, j), getid(i, j - ), INF);
}
}
}
ans -= Dinic();
printf("%d\n", ans);
return ;
}