题解：P6700 [PA 2015 Final] Edycja

· · 题解

更好的阅读体验

打模拟赛打到的，实在是神题阿。

出于一些惯例，我们假设读入的两个字符串分别是 S 和 T。那么经过观察，我们能够发现，一定存在一种最优方案，使所有操作 1 在所有操作 2 的后面。

假设存在一种 1 在 2 前面的操作序列，比如先令 S_k = x，然后将所有 x 变成 y。那么这两个操作可以等效成，先将所有 x 变成 y，然后将 S_k 变成 y。

那么考虑按照字母建点。我们假设 w(x, y) 表示，初始的所有字母 x 在所有 2 操作结束后全部变成了字母 y 的情况下，初始时的所有字母 x 全部和字符串 T 对应位置相等，的最小代价。

刚刚那句话很拗口，举一个例子来帮助理解。如 S = \text{{\color{red}a}b{\color{red}a}{\color{red}a}bb}, T = \text{bbbaaa}。假设我们要求 w(\text{a}, \text{b})，那么就要将 S 中所有字母 \text{a} 转换成 \text{b} 后变成 S' = \text{{\color{red}b}b{\color{red}b}{\color{red}b}bb}，然后看 S' 的红色位置中，有多少个和 T 的对应位置不相等，则这些位置就是我们需要使用操作 1 逐个修改的，容易发现这样的位置有 1 个。因此 w(\text{a}, \text{b}) = c+1。由这个例子可以看出，

w(x, y) = [x \not = y] \cdot c + \sum_{i=1}^n [S_i = x \land T_i \not = y]

注意当 x=y 时不需要进行 2 操作，不会额外产生 c 的代价。

那么我们假设字母 x 最终变成了 to_x，我们在以字母为节点的图上，连接一条有向边 x \to to_x。则问题可以转化成，有一个内向基环树森林，初始节点 i 上有一个编号为 i 的棋子。我们可以给所有边确定一个顺序，然后依次对每条边 x \to y 进行操作，操作形如“将 x 节点上的所有棋子移动到 y 节点上”。要求所有边操作结束后，编号为 i 的棋子在节点 to_i 上。值得注意的是，当两个棋子会合到同一个节点后，它们将不可能分开。

那么假如已经知道了这个内基环树森林的形态，要如何计算这个局面的代价呢？我们根据每个连通块的形态来分类讨论。

Case 1：树

当连通块中存在一个自环，基环树退化成一个有根树，自环的节点为根，如图。

那么这种情况是容易的。首先我们操作根节点，然后剩余的节点按照逆拓扑序操作即可。除了根的儿子以外，其他节点 x 经过一条边跳到 to_x 的时候一定会跳到一个无棋子的节点，因此必然不存在冲突。

假设 w(x, y) 为节点 x, y 之间的边权，这种情况的代价就是所有边的边权之和。

Case 2：未退化基环树

当连通块的环不是自环，且存在入度为 0 的节点，我们称它是一个未退化的基环树，如图。

在这种情况下，环以外的部分同样可以像树的情况一样，按照逆拓扑序操作；但是由于存在一个大小 > 1 的环，因此环上一定存在一个点 x，将 x 上的棋子移动到 to_x 时，to_x 非空。

那么我们找到一个 x 使 to_x 的入度 >1，由于基环树未退化，这样的 x 一定是存在的。那么我们考虑选取一个 y 使得 to_y = to_x 且 y 不在环上。我们可以事先通过一次 2 操作将 x 上的棋子移动到 y 上（因为 to_x = to_y，这个操作不会引起冲突。）这样就说明我们将 x \to to_x 这条边砍掉了，图就变成了一棵树，且此时节点 x 空出来了，作为树的根节点。那么这个时候我们调用树的做法，按照逆拓扑序移动即可。

分析一下代价：由于我们砍掉了一条边，少花费了 c 的代价；但是又多进行了一次 2 操作，而其他的边和边权不变。因此这种情况的代价仍然是所有边的边权之和。

Case 3：未退化的纯环

当这个连通块的大小 >1 且每个节点的入度恰好为 1，我们称它是一个未退化的纯环，如图。

我们仍然希望找到一个中转点，将环断成链。但是由于该连通块中不存在环以外的点，因此我们必须从其他连通块选择任意一个被空出来过的点，记为 y。我们在环上任意选择一个 x。那么当 y 被空出来时，我们先将 x 上的棋子转移到 y 上，然后环就被断成了一个链，我们按照链的逆拓扑序将链上的棋子移动，最后将 y 上的棋子转移到 to_x 上。

容易发现我们在环上少进行了一次 2 操作，但是我们在环外多进行了两次 2 操作，因此一个环的代价是环上所有边的边权之和，再加 c。

注意在这种情况下，我们要选择一个被空出来过的点作为中转点。当这种点不存在的时候无解。因此图中必须存在至少一个未退化的树或基环树。

Case 4：自环

这种情况非常简单，直接移动即可，代价为自环的边权。

综上所述，整张图的权值就是，所有 w(i, to_i) 之和，再加上大小 >1 的环的个数 \times c！

直接构造一个上述权值最小的环并不容易。我们考虑先找出一个代价较小的图，再在其上调整。

我们选 to_i 为 i 边权最小的出边。这里有一个结论：无论我们如何调整出边，都不会产生原图不存在的环。

考虑调整法：假设产生了一个新环，则环的个数一定不会减少；而选择了一些 to_i 使 to_i 不是 i 的最小出边。那么我们将这些边改回去，总代价一定不会变小。

既然只有原有的环，我们就可以 dp 了。我们称一个环被破坏，就是说它被断成了链，或者挂上了一些东西变成了基环树。假设 f_{i, S, 0/1} 表示，当前要给第 i 个点确定出边，当前已经被破坏了的环的集合是 S，当前有没有边被修改（是为了规避前文讲述的无解情况）。那么我们直接枚举出边 \to j，判断 i 所在的环和 j 所在的环有没有被破坏即可。

注意到我们 dp 的环一定大小 >1，因此 |S| 最大只有 13！

那么这道题就做完了，复杂度 O(n + |\Sigma|^2 2^{|\Sigma| / 2})。

#include<bits/stdc++.h>
#define endl '\n'
#define N 1000006
using namespace std;
template <typename T> inline void chkmax(T &x,T y) {x=x<y?y:x;}
template <typename T> inline void chkmin(T &x,T y) {x=x<y?x:y;}
using i64=long long;
int n,c,tot,no_leaf=1,bel[30],cnt[30][30],w[30][30],to[30],in[30];
i64 f[30][1<<16][2];
char s[N],t[N];
main()
{
    scanf("%d%d%s%s",&n,&c,s+1,t+1);
    for(int i=1;i<=n;i++)cnt[s[i]-'a'][t[i]-'a']++;
    for(int i=0;i<26;i++)
    {
        int sum=0;
        for(int j=0;j<26;j++)sum+=cnt[i][j];
        for(int j=0;j<26;j++)
            w[i][j]=sum-cnt[i][j]+(i==j?0:c);
        for(int j=1;j<26;j++)
            if(w[i][j]<w[i][to[i]])to[i]=j;
        in[to[i]]++;
    }
    queue<int> q;
    for(int i=0;i<26;i++)
        if(!in[i])q.push(i),no_leaf=0;
    while(q.size())
    {
        int u=q.front(); q.pop();
        if(!--in[to[u]])q.push(to[u]);
    }
    memset(bel,-1,sizeof(bel));
    for(int i=0;i<26;i++)if(in[i]&&to[i]!=i)
    {
        int j=i;
        while(in[j])in[j]=0,bel[j]=tot,j=to[j];
        tot++;
    }
    if(!tot)
    {
        i64 ans=0;
        for(int i=0;i<26;i++)ans+=w[i][to[i]];
        printf("%lld\n",ans);
        return 0;
    }
    memset(f,0x3f,sizeof(f)),f[0][0][0]=0;
    for(int i=0;i<26;i++)
        for(int S=0;S<(1<<tot);S++)
    {
        for(int o=0;o<2;o++)
            for(int j=0;j<26;j++)
            {
                int nxt=S;
                if(bel[i]!=-1&&to[i]!=j)nxt|=1<<bel[i];
                if(bel[j]!=-1&&(to[i]!=j||bel[i]!=bel[j]))nxt|=1<<bel[j];
                chkmin(f[i+1][nxt][o|(to[i]!=j)],f[i][S][o]+w[i][j]);
            }
    }
    i64 ans=2e18;
    for(int S=0;S<(1<<tot);S++)
        for(int o=no_leaf;o<2;o++)chkmin(ans,f[26][S][o]+(tot-__builtin_popcount(S))*c);
    printf("%lld\n",ans);
    return 0;
}