算法1

最大权闭合子图，需要将费用分成两部分计算

时间复杂度

参考文献

C++ 代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;

#define x first
#define y second

const int C = 110, N = C * C + C, M = (N * 5 + 10) * 2, INF = 0x3f3f3f3f;
int h[N], e[M], ne[M], f[M], idx;
int g[C][C];
int id[C][C], cnt;
int q[N], hh, tt;
int d[N], cur[N];
int a[C];
int n, m, S, T;

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], f[idx] = c, h[a] = idx ++;
    e[idx] = a, ne[idx] = h[b], f[idx] = 0, h[b] = idx ++;
}

bool bfs()
{
    memset(d, -1, sizeof d);
    hh = 0, tt = 0;
    d[S] = 0, q[0] = S, cur[S] = h[S];
    while(hh <= tt)
    {
        int t = q[hh ++ ];
        for(int i = h[t]; ~i; i = ne[i])
        {
            int v = e[i];
            if(d[v] == -1 && f[i])
            {
                d[v] = d[t] + 1;
                cur[v] = h[v];
                if(v == T) return true;
                q[++ tt ] = v;
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if(u == T) return limit;
    int flow = 0;
    for(int i = cur[u]; ~i && flow < limit; i = ne[i])
    {
        int v = e[i];
        cur[u] = i;
        if(d[v] == d[u] + 1 && f[i])
        {
            int r = find(v, min(f[i], limit - flow));
            if(!r) d[v] = -1;
            f[i] -= r, f[i ^ 1] += r, flow += r;
        }
    }
    return flow;
}

int dinic()
{
    int res = 0;
    while(bfs()) res += find(S, INF);
    return res;
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
    for(int i = 1; i <= n; ++ i)
        for(int j = i; j <= n; ++ j)
            scanf("%d", &g[i][j]);
    for(int i = 1; i <= n; ++ i)
        for(int j = i; j <= n; ++ j)
            id[i][j] = ++ cnt;
    map<int, int> st;
    S = 0, T = N - 1;
    memset(h, -1, sizeof h);
    for(int i = 1, t = 0; i <= n; ++ i)
        if(!st.count(a[i]))
        {
            ++ t;
            add(id[i][i], cnt + t, INF);
            st[a[i]] = cnt + t;
        }
        else add(id[i][i], st[a[i]], INF);
    for(int l = 1; l <= n; ++ l)
        for(int r = l; r <= n; ++ r)
            if(l < r)
            {
                add(id[l][r], id[l + 1][r], INF),
                add(id[l][r], id[l][r - 1], INF);
            }
    for(auto &p: st)
    {
        add(p.y, T, m * p.x * p.x);
    }
    for(int i = 1; i <= n; ++ i)
        g[i][i] -= a[i];
    int tot = 0;
    for(int i = 1; i <= n; ++ i)
        for(int j = i; j <= n; ++ j)
            if(g[i][j] > 0)
            {
                add(S, id[i][j], g[i][j]);
                tot += g[i][j];
            }
            else if(g[i][j] < 0)
                add(id[i][j], T, -g[i][j]);
    printf("%d", tot - dinic());
    return 0;
}