「ABC374G」 Only One Product Name

题意

给 \(n\) 个长度为 \(2\)，互不相同，且只由大写字母组成的字符串 \(s\)。

你需要构造出一个字符串数组 \(t\)，使得对于每一个 \(s_i\)，存在 \(t_j\) 使得 \(s_i\) 为 \(t_j\) 的一个连续子串。并且对于每一个 \(t_j\)，它的任意一个连续长度为 \(2\) 的子串都在 \(s\) 中。

求出数组 \(t\) 大小的最小值。

分析

考虑把符合条件的串接起来，这就很像接龙。

一个比较明显的思路就是把尾和头相同的 \(s\) 连边，然后去找最少需要几条路径可以覆盖全部点，就是网络流的最小可相交路径覆盖的板子。

因为原图可能有环，所以缩点之后重新连边，传递闭包后直接跑 dinic 就可以了。

赛时代码写的不可相交，赛后改了 10min 就过了。。。

Code

#include<bits/stdc++.h>
typedef int ll;
using namespace std;
// static char buf[100],*p1=buf,*p2=buf,obuf[100],*p3=obuf;
// #define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,100,stdin),p1==p2)?EOF:*p1++
// #define putchar(x) (p3-obuf<100)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());
#define dbg(x) cout<<#x<<": "<<x<<"\n"
inline ll read(){ll x=0,f=1;char c=getchar();while(c<48||c>57){if(c==45)f=0;c=getchar();}while(c>47&&c<58)x=(x<<3)+(x<<1)+(c^48),c=getchar();return f?x:-x;}
inline void write(ll x){if(!x){putchar(48);putchar('\n');return;}short top=0,s[40];if(x<0)x=-x,putchar(45);while(x)s[top++]=x%10^48,x/=10;while(top--)putchar(s[top]);putchar('\n');}
namespace tobe{
    const ll maxn=1e3+5,maxt=2e6+5,mod=998244353;
    ll n,s,t,tot=1,head[maxn],lvl[maxn],now[maxn];
    string str[maxn];
    struct edge{
        ll to,nxt,val;
    }e[maxt];
    inline void add(ll u,ll v,ll w){
        e[++tot]=(edge){v,head[u],w};
        head[u]=tot;
        e[++tot]=(edge){u,head[v],0};
        head[v]=tot;
    }
    inline bool bfs(){
        memset(lvl,0,sizeof(lvl));lvl[s]=1;
        queue<ll>q;q.push(s);now[s]=head[s];
        while(!q.empty()){
            ll u=q.front();q.pop();
            for(ll i=head[u];i;i=e[i].nxt){
                ll v=e[i].to,w=e[i].val;
                if(w>0&&!lvl[v]){
                    lvl[v]=lvl[u]+1;
                    q.push(v);now[v]=head[v];
                    if(v==t)return 1;
                }
            }
        }
        return 0;
    }
    inline ll dfs(ll u,ll f){
        if(u==t)return f;
        ll tmp=f;
        for(ll i=now[u];i&&tmp;i=e[i].nxt){
            ll v=e[i].to,w=e[i].val;now[u]=i;
            if(w&&lvl[v]==lvl[u]+1){
                ll k=dfs(v,min(w,tmp));
                if(!k)lvl[v]=0;
                e[i].val-=k,e[i^1].val+=k;
                tmp-=k;
            }
        }
        return f-tmp;
    }
    ll dfn[maxn],low[maxn],tmp,cnt,col[maxn],siz[maxn];
    bool vis[maxn],f[maxn][maxn];
    vector<ll>son[maxn];
    stack<ll>st;
    inline void tarjan(ll u){
        dfn[u]=low[u]=++tmp,vis[u]=1;st.push(u);
        for(auto v:son[u]){
            if(!dfn[v]){
                tarjan(v);low[u]=min(low[u],low[v]);
            }
            else if(vis[v])low[u]=min(low[u],dfn[v]);
        }
        if(dfn[u]==low[u]){
            ++cnt;
            while(st.top()!=u)col[st.top()]=cnt,++siz[cnt],vis[st.top()]=0,st.pop();
            col[u]=cnt,vis[u]=0,st.pop();
        }
    }
    inline void mian(){
        n=read();
        for(ll i=1;i<=n;++i){
            cin>>str[i];
        }
        for(ll i=1;i<=n;++i){
            for(ll j=1;j<=n;++j){
                if(str[i][1]==str[j][0]){
                    son[i].push_back(j);
                }
            }
        }
        for(ll i=1;i<=n;++i)if(!dfn[i])tarjan(i);
        s=0,t=cnt*2+1;
        for(ll i=1;i<=n;++i){
            for(auto j:son[i]){
                if(col[i]!=col[j]){
                    f[col[i]][col[j]]=1;
                }
            }
        }
        for(ll k=1;k<=cnt;++k){
            for(ll i=1;i<=cnt;++i){
                for(ll j=1;j<=cnt;++j){
                    f[i][j]|=f[i][k]&f[k][j];
                }
            }
        }
        for(ll i=1;i<=cnt;++i){
            add(s,i,1),add(i+cnt,t,1);
            for(ll j=1;j<=cnt;++j){
                if(f[i][j])add(i,j+cnt,1);
            }
        }
        ll ans=0;
        while(bfs())ans+=dfs(s,INT_MAX);
        write(cnt-ans);
    }
}
signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ll t=1;
    while(t--)tobe::mian();
    // fwrite(obuf,p3-obuf,1,stdout);
    return 0;
}