CF1383C - String Transformation 2

题目大意

给定串\(A,B\)，字符集为前20个小写字母

每次操作取\(A\)中同种字符\(x\)的一个子集，全部改成另一个字符\(y\)

求最少操作次数，使得\(A\)变成\(B\)

分析

图论模型

容易发现，每个\(A_i\rightarrow B_i\)可以看做一条有向边，操作也是如此

那么问题实际上就是：

求一个最少条边的有向图，每条边有一个编号\(i\)

使得对于每一对\(A_i\rightarrow B_i\)，均存在一个编号递增的有向路径

暴力求解

先对于\(A_i\rightarrow B_i\)建立有向图

考虑对于每一个弱连通块，最后形成的图中这些点也必然构成弱连通块

那么一定可以在最终的弱连通块中提取一棵生成树（忽略边的方向）

又可以对于生成树按照边的拓扑序排列，构成一条长链，这样的构造一定不劣

那么分析可行的方案：

1.对于每个弱连通块，先定一条链

2.对于链上的反边所构成的连通块，只需要考虑对于每个新的连通块生成一条链即可

由于范围极小，只有20个点，可以直接状压这条链

对于剩余的连通块，在计算答案时可以考虑对于每个连通块中编号最小的点不算入答案

由于反图的边都是逆着当前的拓扑序的，所以编号最小的点就是没有边连向前面的点

也就是\(dp\)最少的，有反边连入的点的个数，复杂度为\(O(2^{20}\cdot 20)\)

不知道有没有可能写多项式复杂度的

const int N=30,M=1e5+10,INF=1e9+10;

int n;
char s[M],t[M];
int dp[1<<20];
int G[N][N],E[N],I[N];

int vis[N],C;
void dfs(int u){
	if(vis[u]) return;
	vis[u]=1,I[C++]=u;
	rep(i,0,19) if(G[u][i] || G[i][u]) dfs(i);
}

int Solve(){
	int A=(1<