P7086 题解

_Ch1F4N_ · 2023-08-06 21:10:42 · 题解

考虑把每个字符串的前 k 位和后 k 位看成点，字符串看成边，那么一个字符串前缀后缀至少有一个是相似群体的前缀后缀，看成这条边的两个端点至少有一个被选中。

那么这就变成了一个最小点覆盖问题。

考虑匈牙利算法算出答案，然后考虑如何构造答案。

考虑右边没有被匹配的点，选中这些点向左边连的点，因此这个点本身就不用被选中，考虑左边刚刚被选中的点，它们在右边匹配的点就不用选了，那么它们在右边匹配的点就进入右边没有被匹配的点相同的流程，如此递归下去，那么左边便利到的点就会被选中，右边被遍历到的点就不会被选中。

如此便可以构造出选中的点，然后再分配字符串到集合即可。

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;

const int maxn = 1e6+114;
const int base = 1145141;
int vis[maxn],match[maxn];
vector<int> edge[maxn],fedge[maxn];
map<int,int> road[2][maxn];
int ans;
int fm[maxn];
bool hungary(int u){
    for(int v:edge[u]){
        if(vis[v]==1) continue;
        vis[v]=1;
        if(match[v]==0||hungary(match[v])==true){
            match[v]=u;
            fm[u]=v;
            return true;
        }
    }
    return false;
}

int pre[maxn],suf[maxn];

int n,k,cnt;
map<int,int> f;
map<int,int> p[2];
vector<int> chifan[2];
int use[maxn][2];

vector<int> answer[2];
map<int,int> pos[2];

int op[maxn][2];
vector<int> OUT[maxn][2];
void dfs(int u,int type){
    if(op[u][type]==1) return ;
    op[u][type]=1;
    if(type==0){
        dfs(fm[u],1);
    }
    else{
        for(int nxt:fedge[u]){
            if(nxt!=match[u]){
                dfs(nxt,0);
            }
        }
    }
}
signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        for(int j=0;j<k;j++){
            pre[i]=pre[i]*base+s[j];
        }
        for(int j=s.size()-1;j>=s.size()-k&&j<s.size();j--){
            suf[i]=suf[i]*base+s[j];
        }
        if(f[pre[i]]==0){
            f[pre[i]]=++cnt;
        }
        if(p[0][f[pre[i]]]==0)
            chifan[0].push_back(f[pre[i]]),p[0][f[pre[i]]]=1;
        if(f[suf[i]]==0){
            f[suf[i]]=++cnt;
        }
        if(p[1][f[suf[i]]]==0)
            chifan[1].push_back(f[suf[i]]),p[1][f[suf[i]]]=1;
        edge[f[pre[i]]].push_back(f[suf[i]]),fedge[f[suf[i]]].push_back(f[pre[i]]);
    }
    for(int i:chifan[0]){
        memset(vis,0,sizeof(vis));
        if(hungary(i)==true) ans++;
    }
    for(int i:chifan[1]){
        if(match[i]==0){
            dfs(i,1);
        }
    }
    for(int i=1;i<=n;i++){
        if(op[f[pre[i]]][0]==1){
            OUT[f[pre[i]]][0].push_back(i);
        }
        else if(op[f[suf[i]]][1]==0){
            OUT[f[suf[i]]][1].push_back(i);
        }
    }
    cout<<ans<<'\n';
    for(int i:chifan[0]){
        if(op[i][0]==1){
            cout<<OUT[i][0].size()<<' ';
            for(int j:OUT[i][0]) cout<<j<<' ';
            cout<<'\n';
        }
    }
    for(int i:chifan[1]){
        if(op[i][1]==0){
            cout<<OUT[i][1].size()<<' ';
            for(int j:OUT[i][1]) cout<<j<<' ';
            cout<<'\n';
        }
    }
    return 0;
}