2019-2020 ACM-ICPC Pacific Northwest Regional Contest (Div. 1)
题目是给定一个字符串集合，求一个最大的集合，该集合中的元素满足不能交换任意两个字符，使之成为集合中的另一个元素。
我们考虑将能交换两个字符使其中一个字符串$s1$变为另一个字符串$s2$,的两个字符串连边。那么题中的条件可以转化为求一个最大的点集，使这个点集中的元素两两没有连边。即求该图的最大独立集。判断两个字符串是否可以连边，我们可以判断两个字符串是否只有两个字符不同。因为所有字符串之间为$anagram$。
我们考虑朴素的最大独立集算法，时间复杂度为$\mathcal{O}(3^{n/3})$，提交后收获一发$TLE$。
我们重新考虑这个问题，我们发现如果1和2连边，1和0两边，即字符串1和2有两个字符相同，1和0有两个字符相同，那么0和2要么相同，要么肯定不存在连边，所以原图是个二分图。
如果一个图是二分图，那么它的最大独立集就是多项式时间可以解决的问题了
$|最大独立集| = |V|-|最大匹配数|$
我们利用匈牙利算法，可以在$\mathcal{O}(V*E)$的时间复杂度内解决问题。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| #include <bits/stdc++.h>
#define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;++i)
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>PII;
const double eps = 1e-8;
const int maxn = 200000 + 5;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
vector<int> vec[600];
string s[600];
int match[600];
int st[600];
bool find(int x){
for(auto it:vec[x]){
if(!st[it]){
st[it] = 1;
if(!match[it] || find(match[it])){
match[it] = x;
return true;
}
}
}
return false;
}
void lianbian(int i,int j){
int sum = 0;
for(int k=0;k<s[i].length();k++){
if(s[i][k]!=s[j][k]){
sum++;
}
}
if(sum == 2){
vec[i].push_back(j);
vec[j].push_back(i);
}
}
int main(){
int n;
cin >> n;
for(int i=1;i<=n;i++){
cin >> s[i];
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
lianbian(i,j);
}
}
int ans = 0;
for(int i=1;i<=n;i++){
memset(st,0,sizeof(st));
if(find(i)) ans++;
}
cout << n-ans/2;
return 0;
}
|