CodeForces 1250E [2-sat]

题目链接:https://codeforces.com/contest/1250/problem/E

解题思路:

首先根据反转的性质有:

       有字符串a,b,a的反转A，b的反转B，如果a和b匹配值为K，那么A和B的值也为K

        同样a和B匹配值为M，那么A和b的匹配值也为M，因此有对称性

那么就可以转换成2-sat问题了，设点i的对立点集是i+n，也就是a和A

       如果i和j不管怎么反转都能匹配，那么他们之间就没有约束关系

       如果i和j不管怎么反转都不匹配，那么直接是无解的

       如果i只能和j匹配，不能和j+n匹配，那么联合i和j，联合i+n,j+n

       如果只能和j+n匹配，那么联合i和j+n,联合i+n,j

这个就可以用并查集维护，然后因为我们需要更少的反转，所以加上加权并查集，选择权值较小的i集合或者i+n集合

#include<bits/stdc++.h>
using namespace std;
const int mx = 100+5;
const int mod = 1e9 + 7; 
typedef long long ll;
int n,m,K;
int fa[mx],siz[mx],ans[mx];
char s[mx][mx];
vector <int> g[mx];
int find(int x) {
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
bool check(int u,int v) {
	int cnt = 0;
	for (int i=0;i<m;i++)
		cnt += s[u][i] == s[v][i];
	return cnt >= K;
}
bool solve() {
	for (int i=0;i<n;i++) {
		for (int j=i+1;j<n;j++) {
			bool ok1 = check(i,j);
			bool ok2 = check(i,j+n);
			if (!ok1 && !ok2) return 0;
			if (ok1 && ok2) continue;
			int fi = find(i),fj = find(j);
			int fi_n = find(i+n),fj_n = find(j+n);
			if (ok2) swap(fj,fj_n);
			if (fi == fj_n) return 0;
			if (fi != fj) {
				fa[fj] = fi;
				siz[fi] += siz[fj];
				fa[fj_n] = fi_n;
				siz[fi_n] += siz[fj_n]; 
			}
		}
	}
	return 1;
}
int main(){
	int t;
	scanf("%d",&t);
	while (t--) {
		scanf("%d%d%d",&n,&m,&K);
		for (int i=0;i<2*n;i++) {
			fa[i] = i;
			siz[i] = i >= n;
			g[i].clear();
		}
		for (int i=0;i<n;i++) {
			scanf("%s",s[i]);
			reverse(s[i],s[i]+m);
			memcpy(s[i+n],s[i],m+1);
			reverse(s[i],s[i]+m);
		}
		bool ok = solve();
		if (!ok) puts("-1");
		else {
			vector <int> ve;
			int tot = 0;
			for (int i=0;i<2*n;i++) {
				int fi = find(i);
				g[fi].push_back(i);
			}
			for (int i=0;i<n;i++) {
				int fi = find(i);
				int fi_n = find(i+n);
				if (fi != i) continue;
				if (siz[fi] <= siz[fi_n]) ve.push_back(fi);
				else ve.push_back(fi_n);
			}
			for (int u : ve) {
				for (int v :g[u])
					if (v >= n) ans[tot++] = v - n + 1;
			}
			if (!tot) puts("0\n");
			else {
				printf("%d\n",tot);
				for (int i=0;i<tot;i++)	
					printf("%d%c",ans[i],i==tot-1?'\n':' ');
			} 
		}
	}
	return 0;
}