Codeforces 844F Anti-Palindromize 最小费用流

Anti-Palindromize

想到网络流就差不多了， 拆拆点， 建建边。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PLL pair<LL, LL>

#define PLI pair<LL, int>

#define PII pair<int, int>

#define SZ(x) ((int)x.size())

#define ull unsigned long long

using namespace std;

const int N =  + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

const double eps = 1e-;

const double PI = acos(-);

int edgenum, S, T;

int head[N], dist[N], pre[N];

bool vis[N];

struct Edge {

    int from, to, cap, flow, cost, next;

} edge[];

void MCMFinit() {

    edgenum = ;

    memset(head, -, sizeof(head));

}

void addEdge(int u, int v, int w, int c) {

    Edge E1 = {u, v, w, , c, head[u]};

    edge[edgenum] = E1;

    head[u] = edgenum++;

    Edge E2 = {v, u, , , -c, head[v]};

    edge[edgenum] = E2;

    head[v] = edgenum++;

}

bool SPFA(int s, int t) {

    queue<int> Q;

    memset(dist, INF, sizeof(dist));

    memset(vis, false, sizeof(vis));

    memset(pre, -, sizeof(pre));

    dist[s] = ; vis[s] = true; Q.push(s);

    while(!Q.empty()) {

        int u = Q.front(); Q.pop(); vis[u] = false;

        for(int i = head[u]; i != -; i = edge[i].next) {

            Edge E = edge[i];

            if(dist[E.to] > dist[u] + E.cost && E.cap > E.flow) {

                dist[E.to] = dist[u] + E.cost;

                pre[E.to] = i;

                if(!vis[E.to]) {

                    vis[E.to] = true;

                    Q.push(E.to);

                }

            }

        }

    }

    return pre[t] != -;

}

void MCMF(int s, int t, int &cost, int &flow) {

    flow = ; cost = ;

    while(SPFA(s, t)) {

        int Min = INF;

        for(int i = pre[t]; i != -; i = pre[edge[i^].to]) {

            Edge E = edge[i];

            Min = min(Min, E.cap - E.flow);

        }

        for(int i = pre[t]; i != -; i = pre[edge[i^].to]) {

            edge[i].flow += Min;

            edge[i^].flow -= Min;

            cost += edge[i].cost * Min;

        }

        flow += Min;

    }

}

int n;

char s[N];

int a[N], b[N];

int cnt[];

int main() {

    MCMFinit();

    scanf("%d", &n);

    S = , T = (n /  + ) *  + n + ;

    int B = (n /  + );

    int G = (n /  + ) * ;

    scanf("%s", s + );

    for(int i = ; i <= n; i++) scanf("%d", &b[i]);

    for(int i = ; i <= n; i++) {

        a[i] = s[i] - 'a' + ;

        cnt[a[i]]++;

    }

    for(int i = , o = ; i <= G; i += B, o++) {

        addEdge(S, i, cnt[o], );

        for(int j = ; j < B; j++) {

            addEdge(i, i + j, , );

            int c1 = a[j] == o ? -b[j] : ;

            int c2 = a[n - j + ] == o ? -b[n - j + ] : ;

            addEdge(i + j, G + j, , c1);

            addEdge(i + j, G + n - j + , , c2);

        }

    }

    for(int i = ; i <= n; i++) addEdge(G + i, T, , );

    int cost = , flow = ;

    MCMF(S, T, cost, flow);

    printf("%d\n", -cost);

    return ;

}

/*

*/