【CF884F】Anti-Palindromize
题意：定义一个串是反回文的，当且仅当对于1<=i<=len,$a_i!=a_{len-i+1}$。
现在给出一个长度为n的串S(n是偶数)，希望得到一个串T，满足T是S的一个排列，且T是反回文的。
给出数组vi，定义一个排列T的美观度为：$\sum\limits_{S_i=T_i}v_i$
现在想知道，所有合法的T中，美观度最大的是多少。
n<=100
题解：直接上建图方法吧。图一共分为4层：S，所有字符，n/2个位置，T
1.S -> 所有字符 容量是这个字符的出现次数，费用0
2.字符a -> 位置b 容量是1
如果b和n-b+1的字符都不是a，那么费用为0
如果b或n-b+1的字符是a，那么费用为v[b]或v[n-b+1]
如果b和n-b+1的字符都是a，那么费用为max(v[b],v[n-b+1])
3.所有位置 -> T 容量2，费用0
跑最大费用最大流即可。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
int n,cnt,S,T,ans;
int to[10000],nxt[10000],head[110],dis[110],pv[110],pe[110],cost[10000],flow[10000],inq[110];
int v[110],s[30];
char str[110];
queue<int> q;
inline void add(int a,int b,int c,int d)
{
to[cnt]=b,nxt[cnt]=head[a],cost[cnt]=c,flow[cnt]=d,head[a]=cnt++;
to[cnt]=a,nxt[cnt]=head[b],cost[cnt]=-c,flow[cnt]=0,head[b]=cnt++;
}
inline int bfs()
{
int i,u;
memset(dis,0xc0,sizeof(dis));
q.push(S),dis[S]=0;
while(!q.empty())
{
u=q.front(),q.pop(),inq[u]=0;
for(i=head[u];i!=-1;i=nxt[i]) if(dis[to[i]]<dis[u]+cost[i]&&flow[i])
{
dis[to[i]]=dis[u]+cost[i],pe[to[i]]=i,pv[to[i]]=u;
if(!inq[to[i]]) inq[to[i]]=1,q.push(to[i]);
}
}
return dis[T]>=-100000;
}
int main()
{
scanf("%d%s",&n,str+1),S=0,T=n/2+27;
int i,j;
for(i=1;i<=n;i++) s[str[i]-'a'+1]++,scanf("%d",&v[i]);
memset(head,-1,sizeof(head));
for(j=1;j<=26;j++)
{
add(S,j,0,s[j]);
for(i=1;i+i<=n;i++)
{
if(str[i]-'a'+1==j&&str[n-i+1]-'a'+1==j) add(j,i+26,max(v[i],v[n-i+1]),1);
else if(str[i]-'a'+1==j) add(j,i+26,v[i],1);
else if(str[n-i+1]-'a'+1==j) add(j,i+26,v[n-i+1],1);
else add(j,i+26,0,1);
}
}
for(i=1;i+i<=n;i++) add(i+26,T,0,2);
while(bfs())
{
ans+=dis[T];
for(i=T;i!=S;i=pv[i]) flow[pe[i]]--,flow[pe[i]^1]++;
}
printf("%d",ans);
return 0;
}