String Transformation 2 [CF659C][图论][Dp]

题目

CF

思路

妙啊
首先，我们连边 $(a_i,b_i)$ ，毫无疑问有20个点

那么一次操作可理解为将某些位置通过边进行一次转移，答案就是边的个数
然后发现可以省略一些边

换句话说对于一个点 $u$ ，设它连接的开始集合点集为 $S$ ，只用保证 $S$ 中的点 $u$ 能通过路径到达即可
但是有时候会有环

结论：
$ans=2?n?S?T$
$S$ 表示最大 $DAG$ (可不联通)，$T$ 表示弱连通图的个数

证明

代码

#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<climits>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
int read(){
    bool f=0;int x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return !f?x:-x;
}
const int MAXN=20;
int fa[MAXN+5];
int Find(int u){
    return fa[u]==u?u:(fa[u]=Find(fa[u]));}
string s,t;
int f[(1<<MAXN)+5];
int tran[MAXN+5];
void Merge(int u,int v){
    u=Find(u),v=Find(v);if(u==v) return ;fa[u]=v;return ;
}
int main(){
    //f[s]:s是否为多个DAGint T=read();while(T--){
    int n=read();cin>>s,cin>>t;memset(f,0,sizeof(f));memset(tran,0,sizeof(tran));for(int i=0;i<20;i++)fa[i]=i;for(int i=0;i<n;i++){
    tran[s[i]-'a']|=(1<<(t[i]-'a'));Merge(s[i]-'a',t[i]-'a');}f[0]=1;int ans=40,Ma=0;for(int i=0;i<20;i++)if(Find(i)==i)ans--;for(int s=0;s<(1<<20);s++){
    if(!f[s]) continue;int cnt=0;for(int i=0;i<20;i++){
    if((1<<i)&s)cnt++;if(tran[i]&s) continue;f[s|(1<<i)]=1;}Ma=max(Ma,cnt);}printf("%d\n",ans-Ma);}return 0;
}