CF1250E The Coronation (并查集)

做的时候想到拆点，但是没想到维护关系的方法。

这题我们考虑一个字符串分成原串和相反串，用i和i+n表示，我们要做的是维护所有串的相对关系，也就是选了某些串就要选其他串

考虑任意两个字符串i,j之间的关系，如果他们不反转和一个反转都是满足要求的，那么就不用约束关系

如果不反转和反装都不能满足要求，那么就肯定不行输出-1

如果要反转才能满足要求，那么将i,j+n合并和i+n，j合并，这里用并查集，表示选了一个就要选另一个

同理如果不反转才能满足要求，那么连接i,j和i+n，j+n

这样我们就得到了很多连通性集合，对于集合中的点，选一个必须选其他全部

因此我们可以考虑加权后，选择集合中反转串最小的。因为每个集合都是独立的，不可能有一个串在两个不同的集合里面

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int N=1e6+10;
const int mod=1e9+7;
int p[N],sz[N];
int n,m,k;
string s[N];
int vis[N];
int find(int x){
    if(p[x]!=x){
        p[x]=find(p[x]);
    }
    return p[x];
}
int check(int a,int b){
    int i,j;
    int tmp1=0,tmp2=0;
    int cnt=0;
    for(i=1,j=1;i<=m;i++,j++){
        if(s[a][i]!=s[b][j]){
            cnt++;
        }
    }
    if(cnt<=k)
        tmp1=1;
    cnt=0;
    for(i=1,j=m;i<=m;i++,j--){
        if(s[a][i]!=s[b][j]){
            cnt++;
        }
    }
    if(cnt<=k)
        tmp2=1;
    if(tmp1&&tmp2)
        return 0;
    if(!tmp1&&tmp2)
        return 1;
    if(tmp1&&!tmp2)
        return 2;
    if(!tmp1&&!tmp2)
        return 3;
}
vector<int> ans;
void solve(){
    int i;
    for(i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            int tmp=check(i,j);
            if(tmp==0)
                continue;
            if(tmp==1){
                int pa=find(i);
                int pb=find(j+n);
                if(pa!=pb){
                    p[pa]=pb;
                    sz[pb]+=sz[pa];
                }
                pa=find(j);
                pb=find(i+n);
                if(pa!=pb){
                    p[pa]=pb;
                    sz[pb]+=sz[pa];
                }
            }
            else if(tmp==2){
                int pa=find(i);
                int pb=find(j);
                if(pa!=pb){
                    p[pa]=pb;
                    sz[pb]+=sz[pa];
                }
                pa=find(j+n);
                pb=find(i+n);
                if(pa!=pb){
                    p[pa]=pb;
                    sz[pb]+=sz[pa];
                }
            }
            else if(tmp==3){
                cout<<-1<<endl;
                return;
            }
        }
    }
    ans.clear();
    for(i=1;i<=n;i++){
        int pa=find(i),pb=find(i+n);
        if(pa==pb){
            cout<<-1<<endl;
            return ;
        }
        if(vis[pa])
            continue;
        if(vis[pb]){
            ans.push_back(i);
            continue;
        }
        if(sz[pa]>sz[pb]){
            ans.push_back(i);
            vis[pb]=1;
        }
        else{
            vis[pa]=1;
        }
    }
    cout<<(int)ans.size()<<endl;
    for(auto x:ans){
        cout<<x<<" ";
    }
    cout<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        int i;
        cin>>n>>m>>k;
        k=m-k;
        for(i=0;i<=2*n;i++){
            p[i]=i;
            vis[i]=0;
            if(i>n)
                sz[i]=1;
            else
                sz[i]=0;
        }
        for(i=1;i<=n;i++){
            cin>>s[i];
            s[i]=" "+s[i];
        }
        solve();
    }
    return 0;
}