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 ;
} /*
*/
上一篇:阿里云 centos7 django + uWSGI+Nginx + python3 部署攻略


下一篇:poj 2533 Longest Ordered Subsequence(dp)