Codeforces ECR #31 F. Anti-Palindromize

問題文

http://codeforces.com/contest/884/problem/F

解法

最小費用流で解ける．
まず，各アルファベットに対応する26個の頂点と，N / 2 個からなる文字列の前半（ないし後半）に対応する頂点をもつグラフをつくる．
それぞれのアルファベットから，文字列の各位置に対して辺を張る．
以下ではアルファベットの頂点番号を N / 2 + (c - 'a') とする．
頂点 N / 2 + (c - 'a') から頂点 i (0 <= i < N / 2) にフローが流れることを，S[i] または S[N - 1 - i] にアルファベット c を配置するということに対応付ける．
こうする時，辺のコストは max(S[i] == c ? b[i] : 0, S[N - 1 - i] == c ? b[N - 1 - i] : 0) とすることができる．
もちろん容量は1である．
source からは各アルファベットに対して辺を張り，コストは0，容量はそれぞれのアルファベットの出現数とする．
また，文字列の各位置に対応する頂点から sink に辺を張るのだが，これはコスト0，容量2としておく．
以上のように辺をはると，同じ頂点 i (0 <= i < N / 2) に対して同じ文字は割り当てられず，それぞれの頂点にちょうど2個のアルファベットを割り当てることができる．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

using weight = int;

constexpr int INF = 1e9;

struct edge {
    int to, cap;
    weight cost;
    int rev;
};

using edges = std::vector<edge>;
using graph = std::vector<edges>;

void add_edge(graph& g, int from, int to, int cap, weight cost) {
    g[from].push_back(edge{to, cap, cost, (int)g[to].size()});
    g[to].push_back(edge{from, 0, -cost, (int)g[from].size()-1});
}

weight min_cost_flow(graph& g, int s, int t, weight f) {
    using P = std::pair<weight, int>;
    weight res = 0;
    std::vector<weight> h(g.size(), 0);
    std::vector<weight> dist(g.size());
    std::vector<int> prevv(g.size()), preve(g.size());
    while(f > 0) {
        std::priority_queue<P, std::vector<P>, std::greater<P>> que;
        std::fill(dist.begin(), dist.end(), INF);
        dist[s] = 0;
        que.push(P{dist[s], s});
        while(!que.empty()) {
            P p = que.top(); que.pop();
            int v = p.second;
            if(dist[v] < p.first) {
                continue;
            }
            for(int i = 0; i < (int)g[v].size(); ++i) {
                edge& e = g[v][i];
                if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
                    dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                    prevv[e.to] = v;
                    preve[e.to] = i;
                    que.push(P{dist[e.to], e.to});
                }
            }
        }
        if(dist[t] == INF) {
            return -1;
        }
        for(int v = 0; v < (int)g.size(); ++v) {
            h[v] += dist[v];
        }

        weight d = f;
        for(int v = t; v != s; v = prevv[v]) {
            d = min(d, g[prevv[v]][preve[v]].cap);
        }
        f -= d;
        res += d * h[t];
        for(int v = t; v != s; v = prevv[v]) {
            edge& e = g[prevv[v]][preve[v]];
            e.cap -= d;
            g[v][e.rev].cap += d;
        }
    }
    return res;
}


int main() {
    int N;
    string S;
    cin >> N >> S;
    vector<int> b(N);
    for(int i = 0; i < N; ++i) {
        cin >> b[i];
    }
    vector<int> cnt(26);
    for(auto c : S) {
        cnt[c - 'a']++;
    }

    graph g(N / 2 + 26 + 2);
    int const source = N / 2 + 26;
    int const sink = source + 1;
    for(int i = 0; i < 26; ++i) {
        add_edge(g, source, N / 2 + i, cnt[i], 0);
    }
    for(int i = 0; i < N / 2; ++i) {
        add_edge(g, i, sink, 2, 0);
        for(int j = 0; j < 26; ++j) {
            int cost = 0;
            if(S[i] - 'a' == j) {
                cost = max(cost, b[i]);
            }
            if(S[N - 1 - i] - 'a' == j) {
                cost = max(cost, b[N - 1 - i]);
            }
            add_edge(g, N / 2 + j, i, 1, -cost);
        }
    }

    cout << -min_cost_flow(g, source, sink, N) << endl;
}