Anti-Palindromize

· 2024-08-17 · # 网络流 # Codeforces # 题解

给定长度为 $n$ 的字符串 $s$ ，要求找出 $s$ 的排列 $t$ 在满足 $\forall i\in [1,n]\cap \mathbb{N}\mid t_i\ne t_{n-i+1}$ 的情况下使 $\sum\limits_{i=1}^{n}b_i\cdot [s_i=t_i]$ 最大。

其中数据范围满足， $1\le n\le 100$ ， $n$ 为偶数且保证有解。

考虑统计出 $s$ 中每个字符出现的次数 $cnt_i$ ，将 $s$ 的一样的字符一起考虑。

将原点 $S$ 向代表第 $i$ 种字符的节点连一条流量为 $cnt_i$ 费用为 $0$ 的边，这样可以保证在最大流量为 $n$ 时新的序列 $t$ 种每种字符出现的次数都是 $cnt_i$ ，也就是保证 $t$ 是 $s$ 的一个排列。

因为需要满足 $t_i\ne t_{n-i+1}$ ，所以考虑将 $t_i$ 和 $t_{n-i+1}$ 合并为 $1$ 个点，接着想每一种字母只连一条容量为 $1$ 的边，这样就保证了到达这个点的流量一定来自两个不同的字母。

考虑连边的边权，如果将 $ch$ 向 $i$ 连一条费用为 $x$ 的边，那么：

x=\max([s_i=x]\cdot b_i,[s_{n-i+1}=x]\cdot b_{n-i+1})

因为如果只有 $s_i=x\vee s_{n-i+1}=x$ ，那么如果一定要在一个地方放 $x$ 那么为了收益最大先让应该将 $x$ 放在与 $s$ 相等的地方，这样就可以获得对应的收益。

如果 $s_i=x\wedge s_{n-i+1}=x$ ，那么肯定应该将 $x$ 放在收益最大的地方，因为另一个地方一定不是 $x$ 所以这样可以让收益最大化。

对于代表 $t_i$ 和 $t_{n-i+1}$ 的节点，将他们连向 $T$ 流量为 $2$ 费用为 $0$ ，这就保证了这对应的 $2$ 和点一定只有 $2$ 个不同的颜色选择了。

所以直接跑一个网络流就可以了，时间复杂度为 $O(n^3\log n)$ ，但是最大流量只有 $100$ 所以快的一批。