D - Swap Free
题目链接：
题意：找一个集合的最大子集，这个集合中不允许互斥，两个字符串能相互转化（串字符交换一次变成另一个串）就算互斥。
思路：最大独立集
定义：选出一些顶点使得这些顶点两两不相邻，则这些点构成的集合称为独立集。找出一个包含顶点数最多的独立集称为最大独立集。
定理：最大独立集 = 所有顶点数 - 最小顶点覆盖 = 所有顶点数 - 最大匹配
就是最大独立集模板题,建好双向边，最后跑出来的匹配数应该是两个集合都跑了一遍匹配，结果cnt要?2
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=505;
char s[maxn][40];
vector<int>G[maxn];
int vis[maxn],matched[maxn],cnt=0,n,m,e;
bool Find(int u)
{for(int i=0; i<G[u].size(); i++){int v=G[u][i];if(vis[v])continue;vis[v]=1;if(!matched[v]||Find(matched[v])){matched[v]=u;return true;}}return false;
}
int Maxmatch()
{memset(matched,0,sizeof matched);for(int i=1; i<=n; i++){memset(vis,0,sizeof vis);if(Find(i))cnt++;}return cnt;
}
int main()
{scanf("%d",&n);for(int i=1; i<=n; i++){scanf("%s",s[i]);}int len=strlen(s[1]);for(int i=1; i<=n; i++){for(int j=i+1; j<=n; j++){int cnt1=0;for(int k=0; k<len; k++){if(s[i][k]!=s[j][k])cnt1++;}if(cnt1==2)G[i].push_back(j),G[j].push_back(i);}}printf("%d\n",n-Maxmatch()/2);
}