题解 CF1383C 【String Transformation 2】

· · 题解

可以将原问题转化为如下问题

给你一张初始无边的图G,存在20个点,分别表示a\rightarrow t的20个字母.现在要求你按时间顺序连边,使得对于每个位置i,从A_i到B_i都存在一条连边时间单调递增的路径,求最小边数.

再构建一张图T表示|A|种限制.\forall i\in[1,|A|],\exist \{A_i,B_i\}\in T

显然,对于T中的每个弱联通块,他们是独立的.这样,我们对每个弱联通块分开讨论.

设这个弱联通块为H,H\subseteq G,设n=|H|

显然,我们可以使用2\times n-2的代价使得这个连通块中的所有限制都被满足.方案如下

  1. 连边1\rightarrow 2,2\rightarrow 3,...,n-1\rightarrow n.
  2. 连边n\rightarrow 1.
  3. 连边1\rightarrow 2,2\rightarrow 3,...,n-2\rightarrow n-1.

不过,这样连边不一定是最优的.

具体的,我们定义 DAG导出子图 为导出子图Q,且满足Q中不存在环,定义 最大DAG导出子图 为包含点数最多的DAG导出子图.

设m表示H的最大DAG导出子图所包含的点数.可以发现,这个弱联通块的代价可以为n\times 2-1-m,接下来给出构造性证明.

将最大DAG导出子图中的点按拓扑序编号为1\rightarrow m,同时将剩下的点编号为m+1\rightarrow n.

  1. 连边1\rightarrow 2,2\rightarrow 3,...,m-1\rightarrow m,m\rightarrow m+1,边数为m.
  2. 连边m+1\rightarrow 1,边数为1.
  3. 按上文提到的连边方法将m+1\rightarrow n连边,边数为(n-m)\times 2-2.

感性理解一下,n\times 2-m-1也是这个弱联通块代价的上界.接下来给出证明.

首先,对于一个w个点的强联通块,他的代价一定是2\times w-2.

然后,根据上面的定义,可以发现整个图相当于一个强连通分量上每个点连出去若干个DAG,所有这些DAG构成最大DAG导出子图.所以n\times 2-m-1就是下界.

至于实现,对于判断一个点集是否是DAG导出子图可以\mathcal{DP}实现.对于一个DAG,钦定再加一个点满足这个点没有边连向DAG中的点.

int n;
char A[100005],B[100005];
int fa[201];
inline int find(int x)
{
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
int mp[22];
int f[1<<20];
bool dfs(int now)
{
    if(now==0)return 1;
    if(f[now]!=-1)return f[now];
    f[now]=0;
    for(int i=1;i<=n;i++)
        if(now>>(i-1)&1)
            if(((mp[i]>>1)&now)==0)
                f[now]|=dfs(now^(1<<(i-1)));
    return f[now];
}
int calc(int x)
{
    int re=0;
    for(int i=0;i<n;i++)
        if(x>>i&1)
            re++;
    return re;
}
void solve()
{
    read(n);
    scanf("%s",A+1);
    scanf("%s",B+1);
    for(int i=1;i<=20;i++)fa[i]=i;
    memset(mp,0,sizeof(mp));
    for(int i=1;i<=n;i++)
    {
        if(A[i]==B[i])continue;
        int fat=find(A[i]-'a'+1),fbt=find(B[i]-'a'+1);
        mp[A[i]-'a'+1]|=1<<(B[i]-'a'+1);
        if(fat==fbt)continue;
        fa[fat]=fbt;
    }
    int ans=0;
    n=20;
    for(int i=1;i<=n;i++)
        if(find(i)==i)
            ans--;
    memset(f,-1,sizeof(f));
    f[0]=1;
    int mx=0;
    for(int i=0;i<(1<<n);i++)
        if(dfs(i))
            mx=max(mx,calc(i));
    ans=ans-mx+n*2;
    printf("%d\n",ans);
}
int main()
{
    int T;read(T);
    while(T--)solve(); 
    return 0;
}